Болотно-преболотная сортировка :: Bogobogosort

Традиционно самой медленной сортировкой считается так называемая болотная сортировка.

Перемешиваем массив до тех пор, пока его элементы не упорядочатся. Временная сложность — O(n x n!).

Разумеется, любой исключительно медленный алгоритм можно сделать ещё менее продуктивным. Если в Bogosort добавить хвостовую рекурсию при проверке подмассивов на упорядоченность, то даже самое гиблое болото можно утопить в ещё более огромной трясине. Ну, а если ещё рекурсивно клонировать проверяемые подмассивы и сортировать их до тех пор пока они не совпадут с оригиналом то многого можно достигнуть и в сложности по памяти.

Алгоритм

Основной порядок действий — такой же как и у Bogosort:

  1. Проверяем, отсортирован ли массив.
  2. Если нет, то перемешиваем его и возвращаемся в пункт 1.

А вот проверка массива на упорядоченность производится следующим образом:

  1. Создаётся копия массива.
  2. Сортируются первые n-1 элементов копии с помощью Bogobogosort.
  3. Проверяется, больше ли в копии n-й элемент чем первые n-1 элементов.
  4. Если нет, то перемешиваем копию массива и возвращаемся в пункт 2.
  5. Если да, то нужно ещё проверить, совпадает ли копия с оригиналом. Если совпадает, значит массив ни смотря ни на что отсортирован, если нет, то перемешиваем копию массива и идём в пункт 2.

Такое изощрённое издевательство над данными практически гарантирует что процесс сортировки будет продолжаться ну очень долго.

Сложность по времени

Сам автор считает, что где-то порядка O(n!n!). При тестировании на массиве из 7 элементов конечного результата он так и не дождался.

Характеристики алгоритма

Название Болотно-преболотная сортировка (Bogobogosort)
Класс Сортировки обменами
Устойчивость Неустойчивая
Сравнения Нет
Сложность по времени Худшая
Средняя O(n!n!)

Ссылки

Хабрахабр: Эзотерические сортировки Дэвида Морган-Мара

Реализация Bogobogosort на JAVA
DM’s Esoteric Programming Languages — Bogobogosort

Bogosort

Хабрахабр: Непрактичные сортировки – бессмысленные и беспощадные
Болотная сортировка в Википедии
Bogosort on Wikipedia
Реализация Bogosort на различных ЯП

Добавить комментарий