Bogosort

Bogosort
Демонстрация принципа работы (детерминированного) алгоритма Bogosort: он перебирает все возможные комбинации, пока массив не будет отсортирован.
Демонстрация принципа работы (детерминированного) алгоритма Bogosort: он перебирает все возможные комбинации, пока массив не будет отсортирован.
Предназначение Алгоритм сортировки
Худшее время Не определено в случае случайного алгоритма, O ( n × n ! ) {\displaystyle O(n\times n!)} в случае детерминированного алгоритма
Лучшее время O ( n ) {\displaystyle O(n)} [1]
Среднее время O ( n × n ! ) {\displaystyle O(n\times n!)} [1]
Затраты памяти O ( 1 ) {\displaystyle O(1)}

Bogosort (от амер. комп. жарг. bogus — неработоспособный, нефункциональный, бесполезный) — неэффективный алгоритм сортировки, используемый только в образовательных целях и противопоставляемый другим, более реалистичным алгоритмам. Bogosort является частным случаем алгоритма Лас-Вегас.

Существуют две версии этого алгоритма: детерминированная версия, которая перебирает все перестановки до тех пор, пока не будет получен отсортированный массив[2][3], и случайная версия, которая случайным образом переставляет свои входные данные.

Если этот алгоритм использовать для сортировки колоды карт, то сначала в нём нужно проверить, лежат ли все карты по порядку, и если не лежат, то случайным образом перемешать её, проверить лежат ли теперь все карты по порядку, и повторять процесс, пока не отсортируется колода.

Среднее время работы алгоритма:

O ( n ⋅ ∑ i = 1 ∞ i n ! ⋅ ( 1 − 1 n ! ) i − 1 ) = O ( n ⋅ n ! ) . {\displaystyle O\left(n\cdot \sum _{i=1}^{\infty }{\frac {i}{n!}}\cdot \left(1-{\frac {1}{n!}}\right)^{i-1}\right)=O(n\cdot n!).}

Пример реализации

Далее приведена реализация такого алгоритма на языке 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 лет.

См. также

Примечания

  1. ↑ 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.
  2. ↑ Kiselyov, Oleg; Shan, Chung-chieh; Friedman, Daniel P.; Sabry, Amr (2005), "Backtracking, interleaving, and terminating monad transformers: (functional pearl)", Proceedings of the Tenth ACM SIGPLAN International Conference on Functional Programming (ICFP '05) (PDF), SIGPLAN Notices, pp. 192—203, doi:10.1145/1086365.1086390, S2CID 1435535, Архивировано из оригинала (PDF) 26 марта 2012, Дата обращения: 22 июня 2011
  3. ↑ Naish, Lee (1986), "Negation and quantifiers in NU-Prolog", Proceedings of the Third International Conference on Logic Programming, Lecture Notes in Computer Science, vol. 225, Springer-Verlag, pp. 624—634, doi:10.1007/3-540-16492-8_111.

Ссылки

  • 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