Межгосударственное регулирование экономических отношений. Роль наднациональных институтов
Лабораторна робота
Вивчення алгоритмів сортування
Мета: Ознайомитися із простими алгоритмами сортування та навчитися
їх програмувати. Засвоїти базові умови тестування програм та вимірювання їх
ефективності.
Хід роботи
Сортування вставками
Сортування вставками - простий алгоритм сортування на основі
порівнянь. На великих масивах є значно менш ефективним за такі алгоритми, як
швидке сортування, пірамідальне сортування та сортування злиттям. Однак, має
цілу низку переваг:
простота у реалізації
ефективний (за звичай) на маленьких масивах
ефективний при сортуванні масивів, дані в яких вже непогано
відсортовані: продуктивність рівна O (n + d), де d - кількість інверсій
на практиці ефективніший за більшість інших квадратичних
алгоритмів (O (n2)), як то сортування вибором та сортування
бульбашкою: його швидкодія рівна n2/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
|
|
Порівняння
|
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 (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);
}
Висновок
Виконуючи цю роботу я ознайомився і навчився писати різні
алгоритми сортування. Існує дуже багато алгоритмів сортування, кожний зі своїми
перевагами, недоліками і ефективні в тому чи іншому випадку, виконання цієї
роботи допомогло мені зрозуміти принципи роботи деяких з них і коли який з них
слід застосовувати.