Алгоритми сортування (стр. 2 из 2)

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

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

Сортування купою - алгоритм сортування на основі порівнянь. Він полягає у побудові купи і за її допомогою виділення наступного елемента відсортованої послідовності. Хоча, на практиці, він трохи повільніший на більшості машин, ніж швидке сортування, у нього є перевага - швидкодія у найгіршому випадку рівна (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&bsol;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&bsol;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&bsol;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&bsol;n",* (a+i)); }

break;

}

}

fclose (f);

}

Висновок

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