Bogosort

Bogosort (также случайная сортировка, сортировка ружья или обезьянья сортировка) является очень неэффективным алгоритмом сортировки. Её используют только в образовательных целях, противопоставляя другим, более реалистичным алгоритмам. Если 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\cdot \;10^{19}$ лет.

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

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

См. также

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