- Bogosort
-
Bogosort (также случайная сортировка, сортировка ружья или обезьянья сортировка) является очень неэффективным алгоритмом сортировки. Её используют только в образовательных целях, противопоставляя другим, более реалистичным алгоритмам. Если bogosort использовать для сортировки колоды карт, то сначала в алгоритме нужно проверить, лежат ли все карты по порядку, и если не лежат, то случайным образом перемешать её, проверить лежат ли теперь все карты по порядку, и повторять процесс, пока не отсортируется колода.
Среднее время работы алгоритма: .
При прохождении цикла один раз в секунду сортировка следующего количества элементов в среднем может занять:
Кол-во элементов 1 2 3 4 5 6 7 8 9 10 11 12 Среднее время 1 с 4 с 18 с 96 с 10 мин 1.2 часов 9.8 часов 3.7 сут 37.8 сут 1.15 лет 13.9 лет 182 года При работе 4-ядерного процессора 2.4 ГГц (9.6 млрд операций в секунду)
Кол-во элементов 10 11 12 13 14 15 16 17 18 19 20 Среднее время 0.0037 с 0.045 с 0.59 с 8.4 с 2.1 мин 33.6 мин 9.7 часов 7.29 сут 139 дней 7.6 лет 160 лет Колода в 32 карты будет сортироваться компьютером, в среднем, лет.
Содержание
Примеры реализации
Си
int correct( int *arr, int size ) { while (--size > 0) if (arr[size - 1] > arr[size]) return 0; return 1; } void shuffle( int *arr, int size ) { int i; for (i = 0; i < size; i++) swap(arr + i, arr + (rand() % size)); } void bogoSort( int *arr, int size ) { while (!correct(arr, size)) shuffle(arr, size); }
Си++
#include <vector> #include <algorithm> void bogoSort(std::vector<int> &arr) { const auto begin = arr.begin(); const auto end = arr.end(); while (!std::is_sorted(begin, end)) std::random_shuffle(begin, end); }
Java
Random random = new Random(); public void bogoSort(int[] n) { while(!inOrder(n))shuffle(n); } public void shuffle(int[] n) { for (int i = 0; i < n.length; i++) { int swapPosition = random.nextInt(i + 1); int temp = n[i]; n[i] = n[swapPosition]; n[swapPosition] = temp; } } public boolean inOrder(int[] n) { for (int i = 0; i < n.length-1; i++) { if (n[i] > n[i+1]) return false; } return true; }
Nemerle
def bogoSort(arr){ def random = System.Random(); def inOrder(i) { | _ when (i < 2) => true | _ when (arr[i - 2] > arr[i- 1]) => false | _ => inOrder(i - 1) } def shuffle(i) { | 1 => () | _ => arr[random.Next(0, arr.Length)] <-> arr[i - 1]; shuffle(i - 1) } unless (inOrder(arr.Length)){ shuffle(arr.Length); bogoSort(arr) } }
Delphi
program Bogosort; {$APPTYPE CONSOLE} uses SysUtils; const n=10; Type Arr=array[1..n] of integer; function InOrder(M:Arr):boolean; var i:Integer; begin for i:=1 to n-1 do begin if M[i]> M[i+1] then begin result:=False; Break; end else Result:=True; end; end; procedure Shuffle(var M:arr); var RandomIndex,temp,i:integer; begin for i:=1 to n do begin RandomIndex:=Random(n)+1; temp:=m[i]; m[i]:=m[RandomIndex]; m[RandomIndex]:=temp; end; end; var TestArray:arr; i:integer; begin Randomize; for i:=1 to n do TestArray[i]:=Random(n*n); while Not InOrder(TestArray) do Shuffle(TestArray); Readln; end.
Perl
my$s=join'',(sort@out); my$out=join '',@out; while($out ne$s){ for(0..$N-1){ my$r=(rand$N*$N)%$N; ($out[$r],$out[$_])=($out[$_],$out[$r]); } $out=join'',@out; }
См. также
В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена.
Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники.
Эта отметка установлена 13 октября 2011.Алгоритмы сортировки Теория Сложность • О-нотация • Отношение порядка • Типы сортировки: Устойчивая • Внутренняя • Внешняя
Алгоритмы Обменные: Пузырьком • Перемешиванием • Гномья • Быстрая • Расчёской • Выбором: Выбором • Пирамидальная • Вставками: Вставками • Шелла • Деревом • Слиянием: Слиянием • Без дополнительной памяти • Без сравнений: Подсчётом • Поразрядная • Блочная • Гибридные: Introsort • Timsort • Прочее: Топологическая • Сети • Непрактичные: Bogosort • Stooge sort • Глупая • Блинная
Категория:- Алгоритмы сортировки
Wikimedia Foundation. 2010.