Bogosort (от амер. комп. жарг. bogus — неработоспособный, нефункциональный, бесполезный) — неэффективный алгоритм сортировки, используемый только в образовательных целях и противопоставляемый другим, более реалистичным алгоритмам. Bogosort является частным случаем алгоритма Лас-Вегас.
Существуют две версии этого алгоритма: детерминированная версия, которая перебирает все перестановки до тех пор, пока не будет получен отсортированный массив., и случайная версия, которая случайным образом переставляет свои входные данные.
Если этот алгоритм использовать для сортировки колоды карт, то сначала в нём нужно проверить, лежат ли все карты по порядку, и если не лежат, то случайным образом перемешать её, проверить лежат ли теперь все карты по порядку, и повторять процесс, пока не отсортируется колода.
Среднее время работы алгоритма:
Пример реализации Далее приведена реализация такого алгоритма на языке C++, причём такая реализация является примером недетерминированного (случайного) алгоритма:#include <utility>
bool correct(int *arr, int size) { while (--size > 0) if (arr[size - 1] > arr[size]) return false; return true; }
void shuffle(int *arr, int size) { for (int i = 0; i < size; ++i) std::swap(arr[i], arr[(rand() % size)]); }
void bogoSort(int *arr, int size) { while (!correct(arr, size)) shuffle(arr, size); }
Производительность
При прохождении цикла один раз в секунду сортировка в среднем может занять: Кол-во элементов Среднее время 1 1 с 2 4 с 3 18 с 4 96 с 5 10 мин 6 1,2 ч 7 9,8 ч 8 3,7 сут 9 37,8 сут 10 1,15 лет 11 13,9 лет 12 182 года
При работе 4-ядерного процессора на частоте 2,4 ГГц (9,6 млрд операций в секунду): Кол-во элементов Среднее время 10 0,0037 с 11 0,045 с 12 0,59 с 13 8,4 с 14 2,1 мин 15 33,6 мин 16 9,7 ч 17 7,29 сут 18 139 сут 19 7,6 лет 20 160 лет
Таким образом, колода в 32 карты будет сортироваться этим компьютером в среднем 2,7⋅1019 лет.
См. также Лас-Вегас (алгоритм) Генераторы псевдослучайных чисел
Примечания
Ссылки Bogosort / Jargon File Max Sherman Bogo-sort is Sort of Slow, June 2013 Hermann Gruber, Markus Holzer, and Oliver Ruepp, Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms, 2007. Rahul Agrawal, https://www.geeksforgeeks.org/bogosort-permutation-sort/ Непрактичные сортировки — бессмысленные и беспощадные / valemak, 18 октября 2013
Категория:Алгоритмы сортировки