Лабораторна робота
Вивчення алгоритмів сортування
Мета: Ознайомитися із простими алгоритмами сортування та навчитися їх програмувати. Засвоїти базові умови тестування програм та вимірювання їх ефективності.
Хід роботи
Сортування вставками
Сортування вставками — простий алгоритм сортування на основі порівнянь. На великих масивах є значно менш ефективним за такі алгоритми, як швидке сортування, пірамідальне сортування та сортування злиттям. Однак, має цілу низку переваг:
простота у реалізації
ефективний (за звичай) на маленьких масивах
ефективний при сортуванні масивів, дані в яких вже непогано відсортовані: продуктивність рівна O (n + d), де d — кількість інверсій
на практиці ефективніший за більшість інших квадратичних алгоритмів (O (n2)), як то сортування вибором та сортування бульбашкою: його швидкодія рівна n2/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 s\n», (end — start) / CLK_TCK);
rez=fopen («rezult. txt»,«wt»);
for (i=0; 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
середнє
Час
10
Пересилан-ня
38
37
41
35
35
37,2
18
63
Порівняння
29
28
32
26
26
28,2
9
54
Час
50
Пересилан-ня
816
647
691
679
668
700,2
98
1323
Порівняння
767
598
642
630
619
651,2
49
1274
Час
200
Пересилан-ня
10003
11251
9802
10387
10455
10379,6--PAGE_BREAK----PAGE_BREAK--
#include
// 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
{
if (a [h]
{
b [i] =a [h];
h++;
}
else
{
b [i] =a [j];
j++;
}
i++;
}
if (h>m)
{
for (k=j; k
{
b [i] =a [k];
i++;
}
}
else
{
for (k=h; k
{
b [i] =a [k];
i++;
}
}
for (k=l; k
}
void MergeSort (int *a, int l, int r)
{
int m;
if (l
{
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
fprintf (rez,"%d\n",* (X+i));
fclose (rez);
getch ();
}Результат роботи сортування злиттям --PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK--
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
#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 ()%30000;
switch (m)
{
case 0: {
for (i=0; i
fprintf (f,"%d\n",* (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,"%d\n",* (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,"%d\n",* (a+i)); }
break;
}
}
fclose (f);
}
Висновок
Виконуючи цю роботу я ознайомився і навчився писати різні алгоритми сортування. Існує дуже багато алгоритмів сортування, кожний зі своїми перевагами, недоліками і ефективні в тому чи іншому випадку, виконання цієї роботи допомогло мені зрозуміти принципи роботи деяких з них і коли який з них слід застосовувати.