Алгоритми сортування (стр. 1 из 2)
Лабораторна робота
Вивчення алгоритмів сортування
Мета: Ознайомитися із простими алгоритмами сортування та навчитися їх програмувати. Засвоїти базові умови тестування програм та вимірювання їх ефективності.
Хід роботи
Сортування вставками
Сортування вставками - простий алгоритм сортування на основі порівнянь. На великих масивах є значно менш ефективним за такі алгоритми, як швидке сортування, пірамідальне сортування та сортування злиттям. Однак, має цілу низку переваг:
простота у реалізації
ефективний (за звичай) на маленьких масивах
ефективний при сортуванні масивів, дані в яких вже непогано відсортовані: продуктивність рівна 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 | |
Кількість порівняннь:
Кількість пересилань:
Швидке сортування
Швидке сортування (англ. Quick Sort) - алгоритм сортування, добре відомий, як алгоритм розроблений Чарльзом Хоаром, який не потребує додаткової пам'яті і виконує у середньому O (n log (n)) операцій. Однак, у найгіршому випадку робить O (n2) порівнянь. Оскільки алгоритм використовує дуже прості цикли і операції, він працює швидше інших алгоритмів, що мають таку ж асимптотичну оцінку складності.
Ідея алгоритму полягає в переставлянні елементів масиву таким чином, щоб його можна було розділити на дві частини і кожний елемент з першої частини був не більший за будь-який елемент з другої. Впорядкування кожної з частин відбувається рекурсивно. Алгоритм швидкого сортування може бути реалізований як у масиві, так і в двозв’язному списку.
Швидкесортування є алгоритмом на основі порівнянь, і не є стабільним.
Код сортування злиттям:
#include <stdio. h>
#include <conio. h>
#include <stdlib. h>
#include <time. h>
// ----------------------------------------------------------------------
void QuickSort (int *arr, int a, int b)
{
int i=a, j=b, m = rand ()% (b-a) +a;
int x = * (arr+m);
do
{
while (i<=b && * (arr+i) < x) i++;
while (j>=a && * (arr+j) > x) j--;
if (i <= j)
{
if (i < j)
{
int buf=* (arr+i);
* (arr+i) =* (arr+j);
* (arr+j) =buf;
}
i++;
j--;
}
} while (i <= j);
if (i < b) QuickSort (arr, i,b);
if (a < j) QuickSort (arr,a,j);
}
// ---------------------------------------------------------------------
void main ()
{
FILE *f;
int *X, N;
clock_t start, end;
N=0;
f=fopen ("massiv. txt","rt");
start= clock ();
while (! feof (f))
{
fscanf (f,"%d",X+N);
N++;
}
QuickSort (X,0,N-1);
end= clock ();
printf ("The time was:%f s\n", (end - start) / CLK_TCK);
start= clock ();
fclose (f);
getch ();
}
| Результат роботи швидкого сортування | |||||||||
| Довжина послідовності | Випадкові | Зростає | Спадає | ||||||
| 312 | 17 | 927 | 85 | 10009 | середнє | ||||
| 10 | Пересилан-ня | 31 | 21 | 35 | 30 | 35 | 30,4 | 6 | 21 |
| Порівняння | 16 | 20 | 11 | 19 | 13 | 15,8 | 23 | 15 | |
| 50 | Пересилан-ня | 258 | 240 | 259 | 240 | 255 | 250,4 | 31 | 107 |
| Порівняння | 186 | 249 | 188 | 171 | 178 | 194,4 | 214 | 213 | |
| 200 | Пересилан-ня | 1219 | 1292 | 1240 | 1227 | 1241 | 1243,8 | 126 | 428 |
| Порівняння | 1130 | 1357 | 1149 | 1377 | 1308 | 1264,2 | 1562 | 1433 | |
| 1000 | Пересилан-ня | 8055 | 7945 | 8038 | 7997 | 8109 | 8028,8 | 642 | 2139 |
| Порівняння | 7697 | 7652 | 6906 | 7161 | 7030 | 7289,2 | 11779 | 9793 | |
| 5000 | Пересилан-ня | 48603 | 47722 | 48371 | 48384 | 48839 | 48383,8 | 3167 | 10664 |
| Порівняння | 47782 | 55603 | 46085 | 48296 | 44447 | 48442,6 | 69909 | 62812 | |
| 10000 | Пересилан-ня | 104555 | 103469 | 103598 | 103603 | 104151 | 103875,2 | 6333 | 263688 |
| Порівняння | 97973 | 106301 | 106409 | 106769 | 106294 | 104749,2 | 148007 | 140384 | |
Кількість пересилань: