Bogosort

Проблема

Формально, отсортированный массив - это просто одна из n! возможных перестановок исходных элементов. Значит, если перебирать случайные перестановки, рано или поздно можно наткнуться на отсортированную. Вопрос в том, сколько на это уйдёт времени - и именно это Бого-сортировка демонстрирует на практике: она не использует никакой информации о порядке элементов, кроме проверки «отсортирован ли массив прямо сейчас».

Решение

Проверяется, отсортирован ли массив. Если да - готово. Если нет, массив перемешивается случайным образом (например, тасованием Фишера - Йетса) и проверка повторяется. Поскольку перемешивание случайно и независимо от предыдущих попыток, число попыток до успеха не ограничено сверху: в среднем требуется порядка n! перемешиваний, а теоретически процесс может продолжаться бесконечно долго.

Как это работает

Число попыток растёт не просто быстро - оно растёт факториально, а это самый быстрый рост среди всех величин, которые обычно встречаются в анализе алгоритмов. Для 5 элементов (как в тренажёре выше) в среднем нужно 5! = 120 попыток - это ещё вполне терпимо. Для 10 элементов - уже 10! = 3 628 800 попыток, то есть около 36 миллионов элементарных операций сравнения при O(n) на попытку.

Дальше рост становится буквально астрономическим. Для 20 элементов среднее число попыток - 20! ≈ 2,43·10¹⁸. При скорости в миллиард попыток в секунду (оптимистичная оценка для современного процессора) сортировка заняла бы порядка 77 лет непрерывной работы. Для сравнения, у merge sort на тех же 20 элементах ушло бы около 20 · log₂ 20 ≈ 86 операций - разница больше чем на 16 порядков величины.

Математически каждая попытка - независимое испытание Бернулли с вероятностью успеха p = 1/n! (ровно одна из n! перестановок отсортирована). Число попыток до первого успеха подчиняется геометрическому распределению, и его математическое ожидание равно 1/p = n! - отсюда и берётся оценка O(n · n!). При этом отдельный конкретный запуск может повезти на первой же попытке или растянуться на порядок дольше среднего - у геометрического распределения большой разброс.

Гарантия завершения тоже вероятностная, а не абсолютная. Вероятность того, что первые k попыток все окажутся неудачными, равна (1 - p)^k и стремится к нулю при k → ∞ - значит, алгоритм завершается с вероятностью 1, но не за гарантированное конечное число шагов. Это тонкое, но важное различие: «почти наверное завершится» - не то же самое, что «завершится за N шагов» - и Бого-сортировка - редкий пример алгоритма, где эта разница видна невооружённым глазом.

Бого-сортировку иногда называют вычислительной иллюстрацией теоремы о бесконечных обезьянах (infinite monkey theorem) - идеи о том, что случайный процесс, повторяемый достаточно долго, рано или поздно произведёт любой конкретный результат, включая полное собрание сочинений Шекспира. Разница в том, что у Бого-сортировки «результат» - это всего одна из n! перестановок, и его можно посчитать и проверить за разумное время только для очень маленьких n.

В сообществе любителей эзотерических алгоритмов существуют шуточные вариации, доводящие идею до абсурда ещё дальше - например, bogobogosort, которая рекурсивно бого-сортирует каждый префикс массива и отбрасывает результат при малейшей неудаче, что делает её на порядки медленнее обычной Бого-сортировки. Такие варианты не несут практической ценности - они существуют как чисто концептуальная шутка о том, «насколько плохо можно было бы сделать ещё хуже».

Педагогическая ценность Бого-сортировки - в контрасте между «продуктивной» и «непродуктивной» случайностью в алгоритмах. Quicksort использует случайный выбор опорного элемента, чтобы избежать конкретного противника - это случайность, снижающая ожидаемую сложность. Бого-сортировка использует случайность, которая не извлекает никакой информации из предыдущих попыток: она не приближается к ответу постепенно, а каждый раз стартует заново - именно поэтому она остаётся плохим алгоритмом, несмотря на корректность.

Нюансы выбора

При объяснении случайных алгоритмов новичкам - как контрастный пример «плохой» случайности рядом с quicksort или skip list, где случайность действительно снижает сложность вместо того, чтобы просто перебирать варианты вслепую.

При демонстрации геометрического распределения на курсах теории вероятностей и статистики - Бого-сортировка даёт наглядный, легко программируемый пример испытаний Бернулли с крошечной вероятностью успеха.

Никогда в production-коде и никогда там, где n превышает буквально несколько элементов - даже как «шутка» в коде она рискует превратиться в реальный источник зависаний, если случайно попадёт на вход с 15+ элементами.

В споре о том, «что вообще значит алгоритм сортировки» - Бого-сортировка формально удовлетворяет определению (корректно завершается и производит отсортированный вывод), что делает её полезным пограничным случаем для обсуждения того, отделяет ли определение алгоритма практичность от корректности.

Как шкала для сравнения «насколько плохих» алгоритмов друг с другом: bubble sort и Бого-сортировка оба формально «плохие», но разница между O(n²) и O(n · n!) огромна - Бого-сортировка задаёт нижнюю границу спектра, относительно которой даже bubble sort выглядит вполне разумным.

Примеры в коде

Название и сама идея Бого-сортировки возникли как шутка в сообществах программистов ещё в 1990-х годах (обсуждения на Usenet-группах вроде comp.programming), задолго до того, как стали фигурировать в современных списках «худших алгоритмов» и мемах - точное происхождение термина, как это часто бывает с интернет-фольклором, установить сложно.

Видео-визуализаторы алгоритмов сортировки (например, проект «Sound of Sorting» Тимо Бингмана, озвучивающий сравнения элементов как звук) почти всегда включают Бого-сортировку - не ради практической пользы, а ради комического контраста: рядом с несколько секундными анимациями quicksort и merge sort она либо зависает, либо завершается результатом чистого везения.

На Rosetta Code и в вики эзотерических языков программирования Бого-сортировка и её пародийные производные (включая bogobogosort) реализованы на десятках языков - это стало своего рода ритуалом сообщества, демонстрирующим синтаксис языка на заведомо бесполезной, но забавной задаче.

В повседневном жаргоне разработчиков фраза «медленнее, чем Бого-сортировка» используется как гиперболическое сравнение при обсуждении неэффективного кода в код-ревью - несмотря на шуточное происхождение, само название стало общепонятной единицей измерения «плохой сложности алгоритма».

Когда применять

• Никогда в реальных задачах - Бого-сортировка существует исключительно как учебный и шуточный пример.
• В обучении, чтобы наглядно показать, зачем нужны продуманные алгоритмы, и сравнить понятие «случайный перебор» с понятием «детерминированная стратегия».

Примеры из практики

• Курсы и вводные лекции по алгоритмам часто упоминают Бого-сортировку как контрпример - «алгоритм», который формально сортирует, но им нельзя пользоваться.
• Интернет-мемы и списки «худших алгоритмов» в сообществе программистов регулярно ссылаются на Бого-сортировку как классический пример анти-паттерна производительности.