Bogosort

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

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

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

$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!).$

При прохождении цикла один раз в секунду сортировка следующего количества элементов в среднем может занять:

Кол-во элементов	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⋅10¹⁹ лет.

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

#include <utility>

bool correct(int *arr, int size) {
    while (--size > 0)
        if (arr[size - 1] > arr[size])
            return true;
    return false;
}

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);
}

См. также

• Лас-Вегас (алгоритм)
• Генераторы псевдослучайных чисел

Ссылки

• 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