Лабораторна робота
Вивчення алгоритмів сортування
Мета: Ознайомитися із простими алгоритмами сортування та навчитися їх програмувати. Засвоїти базові умови тестування програм та вимірювання їх ефективності.
Хід роботи
Сортування вставками
Сортування вставками - простий алгоритм сортування на основі порівнянь. На великих масивах є значно менш ефективним за такі алгоритми, як швидке сортування, пірамідальне сортування та сортування злиттям. Однак, має цілу низку переваг:
простота у реалізації
ефективний (за звичай) на маленьких масивах
ефективний при сортуванні масивів, дані в яких вже непогано відсортовані: продуктивність рівна 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
Час виконання:
Кількість порівняннь:
Кількість пересилань:
Сортування злиттям
Сортування злиттям - алгоритм сортування, в основі якого лежить принцип Розділяй та володарюй. В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. ............
