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

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

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

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

Хід роботи

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

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

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

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

ефективний при сортуванні масивів, дані в яких вже непогано відсортовані: продуктивність рівна 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

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);

}

Висновок

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