Лабораторная работа: Алгоритми сортування
Лабораторная работа: Алгоритми сортування
Лабораторна робота
Вивчення алгоритмів сортування
Мета: Ознайомитися із простими алгоритмами сортування та навчитися їх програмувати. Засвоїти базові умови тестування програм та вимірювання їх ефективності.
Хід роботи
Сортування вставками
Сортування вставками - простий алгоритм сортування на основі порівнянь. На великих масивах значно менш ефективним за такі алгоритми, як швидке сортування, пірамідальне сортування та сортування злиттям. Однак, має цілу низку переваг:
простота у реалізації
ефективний (за звичай) на маленьких масивах
ефективний при сортуванні масивів, дані в яких вже непогано відсортовані: продуктивність рівна O (n + d), де d - кількість інверсій
на практиц ефективніший за більшість інших квадратичних алгоритмів (O (n2)), як то сортування вибором та сортування бульбашкою: його швидкодія рівна n2/4, в найкращому випадку є лінійною є стабільним алгоритмом
Код програми сортування вставками:
#include <stdio. h>
#include <conio. h>
#include <stdlib. h>
#include <time. h>
// Insertion-------------------------------------------------------------
void Insertion (int *arr, int n)
{
int i,j,buf;
clock_t start, end;
FILE *rez;
start = clock ();
for (i=1; i<n; i++)
{
buf=* (arr+i);
for (j=i-1; j>=0 && * (arr+j) >buf; j--)
* (arr+j+1) =* (arr+j);
* (arr+j+1) =buf;
}
end = clock ();
printf ("The time was:%f s\n", (end - start) / CLK_TCK);
rez=fopen ("rezult. txt","wt");
for (i=0; i<n; i++)
fprintf (rez,"%d\n",* (arr+i));
fclose (rez);
}
// ---------------------------------------------------------------------
void main ()
{
FILE *f;
int *X, N;
clock_t start, end;
f=fopen ("massiv. txt","rt");
N=0;
while (! feof (f))
{
fscanf (f,"%d",X+N);
N++;
}
fclose (f);
clrscr ();
Insertion (X,N);
getch ();
}
Результат роботи сортування вставками | |||||||||
Довжина послідовності | Випадкові | Зростає | Спадає | ||||||
312 | 17 | 927 | 85 | 10009 | середнє | ||||
Час | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
10 | Пересилан-ня | 38 | 37 | 41 | 35 | 35 | 37,2 | 18 | 63 |
Порівняння | 29 | 28 | 32 | 26 | 26 | 28,2 | 9 | 54 | |
Час | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
50 | Пересилан-ня | 816 | 647 | 691 | 679 | 668 | 700,2 | 98 | 1323 |
Порівняння | 767 | 598 | 642 | 630 | 619 | 651,2 | 49 | 1274 | |
Час | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
200 | Пересилан-ня | 10003 | 11251 | 9802 | 10387 | 10455 | 10379,6 | 398 | 20298 |
Порівняння | 9804 | 11052 | 9603 | 10188 | 10256 | 10180,6 | 199 | 20099 | |
Час | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
1000 | Пересилан-ня | 255877 | 250330 | 249604 | 249928 | 252295 | 251606,8 | 1998 | 501498 |
Порівняння | 254879 | 249331 | 248605 | 248929 | 251296 | 250608 | 999 | 500499 | |
Час | 0,054 | 0,055 | 0,054 | 0,054 | 0,55 | 0,054 | 0 | 0,1 | |
5000 | Пересилан-ня | 6302053 | 6183921 | 6229604 | 6391053 | 6282323 | 6277791 | 9998 | 12507498 |
Порівняння | 6297054 | 6178922 | 6224605 | 6386054 | 6277324 | 6272792 | 4999 | 12502499 | |
Час | 0,21 | 0,21 | 0,21 | 0,21 | 0,22 | 0,21 | 0 | 0,44 | |
10000 | Пересилан-ня | 25166644 | 24940616 | 24897941 | 24822544 | 24963312 | 24958211 | 19998 | 50014998 |
Порівняння | 25156645 | 24930617 | 24887942 | 24812545 | 24953313 | 24948212 | 9999 | 50004999 |
Час виконання:
Кількість порівняннь:
Кількість пересилань:
Сортування злиттям
Сортування злиттям - алгоритм сортування, в основі якого лежить принцип Розділяй та володарюй. В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається - тоді решта іншо колони додається до нової.
Під час сортування в дві допоміжні черги з основної поміщаються перші дві відсортован підпослідовності, які потім зливаються в одну і результат записується в тимчасову чергу.
Потім з основно черги беруться наступні дві відсортовані підпослідовності і так до тих пір доки основна черга не стане порожньою. Після цього послідовність з тимчасової черги переміщається в основну чергу. І знову продовжується сортування злиттям двох відсортованих підпослідовностей.
Сортування триватиме до тих пір поки довжина відсортованої підпослідовності не стане рівною довжині самої послідовності.
Код сортування злиттям:
#include <stdio. h> #include <conio. h> #include <stdlib. h> #include <time. h> // Merge----------------------------------------------------------------- void merge (int *a, int l, int m, int r) { int h, i,j,b [10000],k; h=l; i=l; j=m+1; while ( (h<=m) && (j<=r)) { if (a [h] <=a [j]) { b [i] =a [h]; h++; } else { b [i] =a [j]; j++; } i++; } if (h>m) { for (k=j; k<=r; k++) { b [i] =a [k]; i++; } } else { for (k=h; k<=m; k++) { b [i] =a [k]; i++; } } for (k=l; k<=r; k++) {a [k] =b [k]; } } void MergeSort (int *a, int l, int r) { int m; if (l<r) { m= (l+r) /2; MergeSort (a,l,m); MergeSort (a,m+1,r); merge (a,l,m,r); } } // ---------------------------------------------------------------------- void main () { FILE *f,*rez; int *X, N; clock_t start, end; clrscr (); f=fopen ("massiv. txt","rt"); N=0; while (! feof (f)) { fscanf (f,"%d",X+N); N++; } fclose (f); start= clock (); MergeSort (X,0,N-1); end= clock (); printf ("The time was:%f s\n", (end - start) / CLK_TCK); rez=fopen ("rezult. txt","wt"); for (int i=0; i<N; i++) fprintf (rez,"%d\n",* (X+i)); fclose (rez); getch (); }Результат роботи сортування злиттям |
Довжина послідовності | Випадкові | Зростає | Спадає | ||||||
312 | 17 | 927 | 85 | 10009 | середнє | ||||
10 | Пересилання | 78 | 78 | 78 | 78 | 78 | 78 | 78 | 78 |
Порівняння | 22 | 22 | 22 | 22 | 22 | 22 | 22 | 22 | |
50 | Пересилання | 568 | 568 | 568 | 568 | 568 | 568 | 568 | 568 |
Порівняння | 257 | 257 | 257 | 257 | 257 | 257 | 257 | 257 | |
200 | Пересилання | 3106 | 3106 | 3106 | 3106 | 3106 | 3106 | 3106 | 3106 |
Порівняння | 818 | 818 | 818 | 818 | 818 | 818 | 818 | 818 | |
1000 | Пересилання | 19974 | 19974 | 19974 | 19974 | 19974 | 19974 | 19974 | 19974 |
Порівняння | 5049 | 5049 | 5049 | 5049 | 5049 | 5049 | 5049 | 5049 | |
5000 | Пересилання | 123644 | 123644 | 123644 | 123644 | 123644 | 123644 | 123644 | 123644 |
Порівняння | 33965 | 33965 | 33965 | 33965 | 33965 | 33965 | 33965 | 33965 | |
10000 | Пересилання | 267262 | 267262 | 267262 | 267262 | 267262 | 267262 | 267262 | 267262 |
Порівняння | 74335 | 74335 | 74335 | 74335 | 74335 | 74335 | 74335 | 74335 |
Кількість порівняннь:
Страницы: 1, 2