Почему случайность здесь заменяет план
Богосорт не пытается найти, какой элемент стоит не на месте, и не строит порядок шаг за шагом. Он действует по схеме «проверка — новая попытка»: сравнивает соседние элементы, чтобы понять, отсортирован ли весь список, и, если обнаруживает беспорядок, случайно переставляет элементы целиком. Затем проверяет результат снова.
Это важно: случайное перемешивание не приближает список к цели постепенно. После неудачной попытки алгоритм не сохраняет удачные части и не использует их как подсказку. Каждая перестановка — новая ставка на то, что весь список случайно сложится правильно.
Шансы быстро тают с ростом списка
Для списка из n различных элементов существует n! возможных порядков — произведение чисел от 1 до n. Только один из них отсортирован. Поэтому при равномерном случайном перемешивании вероятность успеха за одну попытку равна 1/n!.
Уже для нескольких элементов возможных перестановок становится много, а с добавлением каждого нового элемента их число умножается снова. Если попытки независимы, алгоритм в конце концов может наткнуться на правильный порядок, но ожидание растёт стремительно; гарантированного предела числа попыток нет. Теоретически ему может не повезти сколько угодно долго.
Зачем вообще нужен такой алгоритм
На практике богосорт — скорее наглядная шутка, чем способ сортировать данные. Он показывает разницу между проверкой результата и эффективным поиском решения: убедиться, что список упорядочен, сравнительно просто, но одни только повторные случайные попытки не делают путь к этому порядку разумнее.
Именно поэтому богосорт полезен как контраст к настоящим алгоритмам сортировки: те используют структуру задачи — сравнивают элементы, разбивают список на части или меняют отдельные позиции, — чтобы систематически сокращать беспорядок. Богосорт же может бесконечно перетасовывать список, хотя каждый раз остаётся всего в одной случайной перестановке от успеха.
