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

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

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

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

Хід роботи

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

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

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

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

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

на практиці ефективніший за більшість інших квадратичних алгоритмів (O (n²)), як то сортування вибором та сортування бульбашкою: його швидкодія рівна n²/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 sn", (end - start) / CLK_TCK);

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

for (i=0; i<n; 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 <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 sn", (end - start) / CLK_TCK);

start= clock ();

fclose (f);

getch ();

}

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

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

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

Сортування купою - алгоритм сортування на основі порівнянь. Він полягає у побудові купи і за її допомогою виділення наступного елемента відсортованої послідовності. Хоча, на практиці, він трохи повільніший на більшості машин, ніж швидке сортування, у нього є перевага - швидкодія у найгіршому випадку рівна (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 sn", (end - start) / CLK_TCK);

fclose (f);

getch ();

}

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

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

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

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

#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,"%dn",* (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,"%dn",* (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,"%dn",* (a+i)); }

break;

}

}

fclose (f);

}

Висновок

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