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

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

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

Хід роботи

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

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

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

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

ефективний при сортуванні масивів, дані в яких вже непогано відсортовані: продуктивність рівна 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 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 (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 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); } Висновок Виконуючи цю роботу я ознайомився і навчився писати різні алгоритми сортування. Існує дуже багато алгоритмів сортування, кожний зі своїми перевагами, недоліками і ефективні в тому чи іншому випадку, виконання цієї роботи допомогло мені зрозуміти принципи роботи деяких з них і коли який з них слід застосовувати. 1. Реферат Анализ движения трудовых ресурсов 2. Реферат Электромагнетизм 3. Реферат Квалификация персонала банка. Стимулирование персонала банка 4. Реферат Межі невротичних розладів 5. Реферат Понятие алкоголизма 6. Реферат Биография В.И.Ленина 7. Реферат Создание и совершенствование системы менеджмента качества образования в ВУЗах 8. Курсовая на тему Г Шмоллер Г Шенберг Л Брентано К Брюхер представители исторической 9. Реферат Стратегическое планирование как основа эффективной детельности туристского предприятия 10. Реферат Статистический анализ ЖКХ Bukvasha Правила Контакты