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

Тип работы:
Лабораторная работа
Предмет:
Программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

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

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

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

Хід роботи

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

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

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

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

ефективний при сортуванні масивів, дані в яких вже непогано відсортовані: продуктивність рівна 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 sn», (end — start) / CLK_TCK);

rez=fopen («rezult. txt»,"wt");

for (i=0; i< n; i++)

fprintf (rez,"%dn",* (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

10 009

середнє

Час

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

Пересилан-ня

10 003

11 251

9802

10 387

10 455

10 379,6

398

20 298

Порівняння

9804

11 052

9603

10 188

10 256

10 180,6

199

20 099

Час

0

0

0

0

0

0

0

0

1000

Пересилан-ня

255 877

250 330

249 604

249 928

252 295

251 606,8

1998

501 498

Порівняння

254 879

249 331

248 605

248 929

251 296

250 608

999

500 499

Час

0,054

0,055

0,054

0,054

0,55

0,054

0

0,1

5000

Пересилан-ня

6 302 053

6 183 921

6 229 604

6 391 053

6 282 323

6 277 791

9998

12 507 498

Порівняння

6 297 054

6 178 922

6 224 605

6 386 054

6 277 324

6 272 792

4999

12 502 499

Час

0,21

0,21

0,21

0,21

0,22

0,21

0

0,44

10 000

Пересилан-ня

25 166 644

24 940 616

24 897 941

24 822 544

24 963 312

24 958 211

19 998

50 014 998

Порівняння

25 156 645

24 930 617

24 887 942

24 812 545

24 953 313

24 948 212

9999

50 004 999

Час виконання:

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

Кількість пересилань:

Сортування злиттям

Сортування злиттям — алгоритм сортування, в основі якого лежить принцип Розділяй та володарюй. В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається — тоді решта іншої колони додається до нової.

Під час сортування в дві допоміжні черги з основної поміщаються перші дві відсортовані підпослідовності, які потім зливаються в одну і результат записується в тимчасову чергу.

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

Сортування триватиме до тих пір поки довжина відсортованої підпослідовності не стане рівною довжині самої послідовності.

Код сортування злиттям:

#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 [10 000], 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 sn», (end — start) / CLK_TCK);

rez=fopen («rezult. txt»,"wt");

for (int i=0; i< N; i++)

fprintf (rez,"%dn",* (X+i));

fclose (rez);

getch ();

}Результат роботи сортування злиттям

Довжина послідовності

Випадкові

Зростає

Спадає

312

17

927

85

10 009

середнє

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

Пересилання

19 974

19 974

19 974

19 974

19 974

19 974

19 974

19 974

Порівняння

5049

5049

5049

5049

5049

5049

5049

5049

5000

Пересилання

123 644

123 644

123 644

123 644

123 644

123 644

123 644

123 644

Порівняння

33 965

33 965

33 965

33 965

33 965

33 965

33 965

33 965

10 000

Пересилання

267 262

267 262

267 262

267 262

267 262

267 262

267 262

267 262

Порівняння

74 335

74 335

74 335

74 335

74 335

74 335

74 335

74 335

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

Кількість пересилань:

Швидке сортування

Швидке сортування (англ. 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 sn», (end — start) / CLK_TCK);

start= clock ();

fclose (f);

getch ();

}

Результат роботи швидкого сортування

Довжина послідовності

Випадкові

Зростає

Спадає

312

17

927

85

10 009

середнє

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

11 779

9793

5000

Пересилан-ня

48 603

47 722

48 371

48 384

48 839

48 383,8

3167

10 664

Порівняння

47 782

55 603

46 085

48 296

44 447

48 442,6

69 909

62 812

10 000

Пересилан-ня

104 555

103 469

103 598

103 603

104 151

103 875,2

6333

263 688

Порівняння

97 973

106 301

106 409

106 769

106 294

104 749,2

148 007

140 384

Кількість пересилань:

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

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

Сортування купою — алгоритм сортування на основі порівнянь. Він полягає у побудові купи і за її допомогою виділення наступного елемента відсортованої послідовності. Хоча, на практиці, він трохи повільніший на більшості машин, ніж швидке сортування, у нього є перевага — швидкодія у найгіршому випадку рівна (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 sn», (end — start) / CLK_TCK);

fclose (f);

getch ();

}

Результат сортування купою

Довжина послідовності

Випадкові

Зростає

Спадає

312

17

927

85

10 009

середнє

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

Пересилання

15 100

15 115

15 040

15 059

15 093

15 081,4

15 708

14 310

Порівняння

18 549

18 561

18 443

18 485

18 485

18 504,6

19 541

17 297

5000

Пересилання

87 068

87 185

87 111

86 934

87 020

87 063,6

90 962

83 326

Порівняння

115 892

116 054

115 947

115 696

115 841

115 886

122 105

109 970

10 000

Пересилання

184 192

184 125

184 244

184 256

184 293

184 222

191 422

176 974

Порівняння

251 886

251 786

251 951

251 920

251 997

251 908

263 688

240 349

Кількість пересилань:

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

Перевірка ефективності алгоритмів

Програма генерації послідовностей:

#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 ()%30 000;

switch (m)

{

case 0: {

for (i=0; i< n; i++)

fprintf (f,"%dn",* (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,"%dn",* (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,"%dn",* (a+i)); }

break;

}

}

fclose (f);

}

Висновок

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

ПоказатьСвернуть
Заполнить форму текущей работой