|
|
Приклад реалізації крок за крокомВізьмемо масив чисел "5 1 4 2 8", і за допомогою даного алгоритму, відсортуємо його від найменшого до найбільшого елементу. На кожному кроці, елементи, виділені жирнимшрифтом будуть порівнюватись. Перший прохід: Застосування алгоритму Хоча, алгоритм є одним із найпростіших алгоритмів сортування, його ефективність є досить низькою, і він погано підходить для сортування великих списків. Більшість інших алгоритмів з такою ж швидкодією O(n2) є ефективнішими за алгоритм сортуванням бульбашками, наприклад, сортування включенням. Через свою простоту, алгоритм часто використовується для пояснення студентам концепції алгоритмів, та алгоритмів сортування, зокрема. Однак, деякі дослідники, як то Оуен Астрахан (Owen Astrachan) ретельно дослідивши даний алгоритм, стверджують, що він настільки поганий і неефективний, що вони навіть не використовуватимуть його в якості прикладу у своїй викладацькій діяльності. Дональд Кнут у своїй знаменитій праці The Art of Computer Programming прийшов до висновку, що "немає жодних підстав рекомендувати використовувати даний алгоритм, окрім, хіба що через примітну назву і через те, що він є лідером у кількості цікавих теоретичних проблем", частину з яких він обговорює у своїй праці. Сортування бульбашкою під час своєї роботи є асимптоматичним еквівалентом алгоритму сортування включенням, у своєму найгіршому випадку, однак, обидва алгоритми дуже сильно відрізняються кількістю необхідних операцій переміщення. Результати низки експериментів, наприклад, проведених Астраханом також підтверджують той факт, що продуктивність алгоритму сортування включенням є значно вищою. Тому багато сучасних посібників з алгоритмів навіть не згадують про алгоритм сортування бульбашками, і віддають перевагу сортуванню включеннями. Сортування бульбашкою також погано використовує можливості сучасних мікропроцесорів. Він вимагає щонайменше удвічі більше операцій, ніж сортування включенням, удвічі більшекеш пам'яті, і асимптоматично більше передбачень переходів. Результати експериментів проведених Астраханом показали, що сортування рядка за алгоритмом сортування бульбашками у п'ять разів повільніше за сортування того ж рядка за алгоритмом сортування включенням і на 40% повільніше за сортування за алгоритмом сортування вибором. Практична частина Програма реалізації алгоритму швидкого сортування
void quickSort(int l, int r) { int x = a[l + (r - l) / 2]; int i = l; int j = r; while(i <= j) { while(a[i] < x) i++; while(a[j] > x) j--; if(i <= j) { count1++; swap(a[i], a[j]); i++; j--; } } if (i<r) quickSort(i, r); if (l<j) quickSort(l, j); }
int main() { int n; cin >> n; for(int i = 0; i < n; i++) { a[i]=rand()%1000; /* або a[i]=i; або a[i]=1000-i;*/ cout<<a[i]<<' '; } cout<<endl; clock_t start = clock(); quickSort(0, n-1); cout<<"Time quicksort ="<<(long double) (clock() - start) / CLOCKS_PER_SEC; for(int i = 0; i < n; i++) cout<<a[i]<<' '; cout<<endl<<"quicksort="<<count1<<endl; system("pause"); return 0; } Програма реалізації алгоритму сортування «бульбашкою»
void bubblesort(int n) { bool t=true; while(t) { t=false; for (int i=0;i<n-1;i++) if (b[i]>b[i+1]) { swap(b[i],b[i+1]); count2++; t=true; } } }
int main() { int n; cin >> n; for(int i = 0; i < n; i++) { b[i]=rand()%1000; /* або b[i]=i; або b[i]=1000-i;*/ cout<<b[i]<<' '; } cout<<endl; clock_t start = clock(); bubblesort(n); cout<<"Time bubble ="<<(long double) (clock() - start) / CLOCKS_PER_SEC;
for(int i = 0; i < n; i++) cout<<b[i]<<' '; cout<<endl<<"bubble="<<count2<<endl; system("pause"); return 0; }
  Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...  ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...  ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...  Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
(1 5 4 2 8) Тут, алгоритм порівнює перші два елементи, і міняє їх місцями.