Лабораторная работа: Алгоритми сортування
Кількість пересилань:
Швидке сортування
Швидке сортування (англ. 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 |
Кількість пересилань:
Кількість порівняннь:
Сортування купою
Сортування купою - алгоритм сортування на основі порівнянь. Він полягає у побудові купи і за допомогою виділення наступного елемента відсортованої послідовності. Хоча, на практиці, він трохи повільніший на більшості машин, ніж швидке сортування, у нього є перевага - швидкодія у найгіршому випадку рівна (n log n). Є не стабільним алгоритмом.
Код сортування злиттям:
#include <stdio. h>
#include <conio. h>
#include <stdlib. h>
#include <time. h>
// Heap------------------------------------------------------------------
void doHeap (int *arr, int k, int n)
{
int c; int a = * (arr+k);
while (k <= n/2)
{
c = 2*k;
if (c < n && * (arr+c) < * (arr+c+1)) c++;
if (a >= * (arr+c)) break;
* (arr+k) = * (arr+c);
k = c;
}
* (arr+k) = a;
}
void HeapSort (int *a, int n)
{
int i;
for (i=n/2; i >= 0; i--) doHeap (a, i, n-1);
for (i = n-1; i > 0; i--)
{
int buf=*a;
*a=* (a+i);
* (a+i) =buf;
doHeap (a,0, i-1);
}
}
// ----------------------------------------------------------------------
void main ()
{
FILE *f;
int *X, N;
clock_t start, end;
clrscr ();
N=0;
f=fopen ("massiv. txt","rt");
while (! feof (f))
{
fscanf (f,"%d",X+N);
N++;
}
start= clock ();
HeapSort (X,N);
end= clock ();
printf ("The time was:%f s\n", (end - start) / CLK_TCK);
fclose (f);
getch ();
}
Результат сортування купою | |||||||||
Довжина послідовності | Випадкові | Зростає | Спадає | ||||||
312 | 17 | 927 | 85 | 10009 | середнє | ||||
10 | Пересилання | 82 | 83 | 83 | 83 | 85 | 83,2 | 86 | 77 |
Порівняння | 54 | 56 | 56 | 56 | 60 | 56,4 | 59 | 46 | |
50 | Пересилання | 532 | 535 | 535 | 535 | 544 | 536,2 | 564 | 497 |
Порівняння | 490 | 495 | 499 | 495 | 508 | 497,4 | 537 | 435 | |
200 | Пересилання | 2567 | 2532 | 2544 | 2555 | 2550 | 2549,6 | 2682 | 2410 |
Порівняння | 2808 | 2758 | 2767 | 2784 | 2785 | 2780,4 | 2984 | 2549 | |
1000 | Пересилання | 15100 | 15115 | 15040 | 15059 | 15093 | 15081,4 | 15708 | 14310 |
Порівняння | 18549 | 18561 | 18443 | 18485 | 18485 | 18504,6 | 19541 | 17297 | |
5000 | Пересилання | 87068 | 87185 | 87111 | 86934 | 87020 | 87063,6 | 90962 | 83326 |
Порівняння | 115892 | 116054 | 115947 | 115696 | 115841 | 115886 | 122105 | 109970 | |
10000 | Пересилання | 184192 | 184125 | 184244 | 184256 | 184293 | 184222 | 191422 | 176974 |
Порівняння | 251886 | 251786 | 251951 | 251920 | 251997 | 251908 | 263688 | 240349 |
Кількість пересилань:
Кількість порівняннь:
Перевірка ефективності алгоритмів
Програма генерац послідовностей:
#include <stdio. h>
#include <stdlib. h>
void main ()
{
FILE *f;
int n;
int i,m,s,*a;
if ( (f=fopen ("massiv. txt","wt")) ! =NULL)
{
printf ("Enter amount of elements ");
scanf ("%d",&n);
printf ("Choos method (0: rand; 1: rand up; 2: rand down)");
scanf ("%d",&m);
printf ("Enter sort combination ");
scanf ("%d",&s);
srand (s);
for (i=0; i<n; i++)
* (a+i) =rand ()%30000;
switch (m)
{
case 0: {
for (i=0; i<n; i++)
fprintf (f,"%d\n",* (a+i)); }
break;
case 1: {
int buf=0;
for (int i=1; i<n; i++)
{
buf=* (a+i);
for (int j=i-1; j>=0 && * (a+j) >buf; j--)
* (a+j+1) =* (a+j);
* (a+j+1) =buf;
}
for (i=0; i<n; i++)
fprintf (f,"%d\n",* (a+i)); }
break;
case 2: {
int buf=0;
for (int i=1; i<n; i++)
{
buf=* (a+i);
for (int j=i-1; j>=0 && * (a+j) <buf; j--)
* (a+j+1) =* (a+j);
* (a+j+1) =buf;
}
for (i=0; i<n; i++)
fprintf (f,"%d\n",* (a+i)); }
break;
}
}
fclose (f);
}
Висновок
Виконуючи цю роботу я ознайомився і навчився писати різні алгоритми сортування. Існує дуже багато алгоритмів сортування, кожний зі своїми перевагами, недоліками ефективні в тому чи іншому випадку, виконання цієї роботи допомогло мен зрозуміти принципи роботи деяких з них і коли який з них слід застосовувати.