Алгоритми сортування

Лабораторна робота

Вивчення алгоритмів сортування

Мета: Ознайомитися із простими алгоритмами сортування та навчитися їх програмувати. Засвоїти базові умови тестування програм та вимірювання їх ефективності.

Хід роботи

Сортування вставками

Сортування вставками — простий алгоритм сортування на основі порівнянь. На великих масивах є значно менш ефективним за такі алгоритми, як швидке сортування, пірамідальне сортування та сортування злиттям. Однак, має цілу низку переваг:

простота у реалізації

ефективний (за звичай) на маленьких масивах

ефективний при сортуванні масивів, дані в яких вже непогано відсортовані: продуктивність рівна O (n + d), де d — кількість інверсій

на практиці ефективніший за більшість інших квадратичних алгоритмів (O (n²)), як то сортування вибором та сортування бульбашкою: його швидкодія рівна n²/4, і в найкращому випадку є лінійною є стабільним алгоритмом

Код програми сортування вставками:

#include

#include

#include

#include

// Insertion——————————————————————————————;

void Insertion (int *arr, int n)

{

int i, j, buf;

clock_t start, end;

FILE *rez;

start = clock ();

for (i=1; 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 sn», (end — start) / CLK_TCK);

rez=fopen («rezult. txt» ," wt");

for (i=0; i

fprintf (rez," %dn" ,* (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 ();

}

Час виконання:

Кількість порівняннь:

Кількість пересилань:

Сортування злиттям

Сортування злиттям — алгоритм сортування, в основі якого лежить принцип Розділяй та володарюй. В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається — тоді решта іншої колони додається до нової.

Під час сортування в дві допоміжні черги з основної поміщаються перші дві відсортовані підпослідовності, які потім зливаються в одну і результат записується в тимчасову чергу.

Потім з основної черги беруться наступні дві відсортовані підпослідовності і так до тих пір доки основна черга не стане порожньою. Після цього послідовність з тимчасової черги переміщається в основну чергу. І знову продовжується сортування злиттям двох відсортованих підпослідовностей.

Сортування триватиме до тих пір поки довжина відсортованої підпослідовності не стане рівною довжині самої послідовності.

Код сортування злиттям:

Кількість порівняннь:

Кількість пересилань:

Швидке сортування

Швидке сортування (англ. Quick Sort) — алгоритм сортування, добре відомий, як алгоритм розроблений Чарльзом Хоаром, який не потребує додаткової пам’яті і виконує у середньому O (n log (n)) операцій. Однак, у найгіршому випадку робить O (n²) порівнянь. Оскільки алгоритм використовує дуже прості цикли і операції, він працює швидше інших алгоритмів, що мають таку ж асимптотичну оцінку складності.

Ідея алгоритму полягає в переставлянні елементів масиву таким чином, щоб його можна було розділити на дві частини і кожний елемент з першої частини був не більший за будь-який елемент з другої. Впорядкування кожної з частин відбувається рекурсивно. Алгоритм швидкого сортування може бути реалізований як у масиві, так і в двозв’язному списку.

Швидке сортування є алгоритмом на основі порівнянь, і не є стабільним.

Код сортування злиттям:

#include

#include

#include

#include

// ———————————————————————————————————

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 sn», (end — start) / CLK_TCK);

start= clock ();

fclose (f);

getch ();

}

Кількість пересилань:

Кількість порівняннь:

Сортування купою

Сортування купою — алгоритм сортування на основі порівнянь. Він полягає у побудові купи і за її допомогою виділення наступного елемента відсортованої послідовності. Хоча, на практиці, він трохи повільніший на більшості машин, ніж швидке сортування, у нього є перевага — швидкодія у найгіршому випадку рівна (n log n). Є не стабільним алгоритмом.

Код сортування злиттям:

#include

#include

#include

#include

// 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 sn», (end — start) / CLK_TCK);

fclose (f);

getch ();

}

Кількість пересилань:

Кількість порівняннь:

Перевірка ефективності алгоритмів

Програма генерації послідовностей:

#include

#include

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

* (a+i) =rand ()%30 000;

switch (m)

{

case 0: {

for (i=0; i

fprintf (f," %dn" ,* (a+i)); }

break;

case 1: {

int buf=0;

for (int i=1; 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

fprintf (f," %dn" ,* (a+i)); }

break;

case 2: {

int buf=0;

for (int i=1; i

{

buf=* (a+i);

for (int j=i-1; j>=0 && * (a+j)

* (a+j+1) =* (a+j);

* (a+j+1) =buf;

}

for (i=0; i

fprintf (f," %dn" ,* (a+i)); }

break;

}

}

fclose (f);

}

Висновок

Виконуючи цю роботу я ознайомився і навчився писати різні алгоритми сортування. Існує дуже багато алгоритмів сортування, кожний зі своїми перевагами, недоліками і ефективні в тому чи іншому випадку, виконання цієї роботи допомогло мені зрозуміти принципи роботи деяких з них і коли який з них слід застосовувати.