|
Алгоритми сортування |
p align="left">Кількість порівняннь: Кількість пересилань: Швидке сортуванняШвидке сортування (англ. 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);}ВисновокВиконуючи цю роботу я ознайомився і навчився писати різні алгоритми сортування. Існує дуже багато алгоритмів сортування, кожний зі своїми перевагами, недоліками і ефективні в тому чи іншому випадку, виконання цієї роботи допомогло мені зрозуміти принципи роботи деяких з них і коли який з них слід застосовувати.
Страницы: 1, 2
|
|
|
© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент. |
|
|