Болотно-преболотная сортировка :: Bogobogosort
Традиционно самой медленной сортировкой считается так называемая болотная сортировка.
Перемешиваем массив до тех пор, пока его элементы не упорядочатся. Временная сложность - O(n x n!).
Разумеется, любой исключительно медленный алгоритм можно сделать ещё менее продуктивным. Если в Bogosort добавить хвостовую рекурсию при проверке подмассивов на упорядоченность, то даже самое гиблое болото можно утопить в ещё более огромной трясине. Ну, а если ещё рекурсивно клонировать проверяемые подмассивы и сортировать их до тех пор пока они не совпадут с оригиналом то многого можно достигнуть и в сложности по памяти.
Алгоритм
Основной порядок действий - такой же как и у Bogosort:
- Проверяем, отсортирован ли массив.
- Если нет, то перемешиваем его и возвращаемся в пункт 1.
- Создаётся копия массива.
- Сортируются первые n-1 элементов копии с помощью Bogobogosort.
- Проверяется, больше ли в копии n-й элемент чем первые n-1 элементов.
- Если нет, то перемешиваем копию массива и возвращаемся в пункт 2.
- Если да, то нужно ещё проверить, совпадает ли копия с оригиналом. Если совпадает, значит массив ни смотря ни на что отсортирован, если нет, то перемешиваем копию массива и идём в пункт 2.
Такое изощрённое издевательство над данными практически гарантирует что процесс сортировки будет продолжаться ну очень долго.
Сложность по времени
Сам автор считает, что где-то порядка O(n!n!). При тестировании на массиве из 7 элементов конечного результата он так и не дождался.
Характеристики алгоритма
| Название | Болотно-преболотная сортировка (Bogobogosort) | |
|---|---|---|
| Класс | Эзотерические сортировки | |
| Устойчивость | Неустойчивая | |
| Сравнения | Нет | |
| Сложность по времени | Худшая | ∞ |
| Средняя | O(n!n!) | |
Ссылки
Эзотерические сортировки Дэвида Морган-Мара
Реализация Bogobogosort на JAVA
DM's Esoteric Programming Languages - Bogobogosort
Болотная сортировка
Реализация Bogosort на различных ЯП