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 карты будет сортироваться компьютером в среднем 2,7⋅1019 лет.
Пример реализации
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);
}
См. также
Ссылки
- 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
Это заготовка статьи по информатике. Вы можете помочь проекту, дополнив её. |
В этой статье не хватает ссылок на источники информации. |