Bogosort

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

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

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

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

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

${\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);
}

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

• 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