Меню
Главная
Случайная статья
Настройки
|
Bogosort (от амер. комп. жарг. bogus — неработоспособный, нефункциональный, бесполезный) — неэффективный алгоритм сортировки, используемый только в образовательных целях и противопоставляемый другим, более реалистичным алгоритмам. Bogosort является частным случаем алгоритма Лас-Вегас.
Существуют две версии этого алгоритма: детерминированная версия, которая перебирает все перестановки до тех пор, пока не будет получен отсортированный массив[2][3], и случайная версия, которая случайным образом переставляет свои входные данные.
Если этот алгоритм использовать для сортировки колоды карт, то сначала в нём нужно проверить, лежат ли все карты по порядку, и если не лежат, то случайным образом перемешать её, проверить лежат ли теперь все карты по порядку, и повторять процесс, пока не отсортируется колода.
Среднее время работы алгоритма:
Содержание
Пример реализации
Далее приведена реализация такого алгоритма на языке 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,71019 лет.
|
См. также
Примечания
- 1 2 Gruber, H.; Holzer, M.; Ruepp, O., Sorting the slow way: an analysis of perversely awful randomized sorting algorithms, 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007 (PDF), Lecture Notes in Computer Science, vol. 4475, Springer-Verlag, pp. 183–197, doi:10.1007/978-3-540-72914-3_17, Архивировано (PDF) 29 сентября 2020, Дата обращения: 25 февраля 2024.
-
-
Ссылки
|
|