Сортировка "Ханойская башня" :: Tower of Hanoi sort
Алгоритм сортировки, основанный на знаменитой головоломке французского математика Эдуарда Люка.
Ханойская башня
Имеется три стержня, на первый из которых нанизаны диски разного диаметра, причём меньшие по размеру диски лежат на более крупных. Разрешается переносить диски с одного стержня на другой, соблюдая при этом два правила:
- За один раз переносится только один диск.
- Разрешается только меньшие по размеру диски ложить на более крупные.
Задача - переместить все диски с первого стержня на последний (средний используется как вспомогательный).Оптимальный рекурсивный алгоритм для решения головоломки имеет временную сложность O(2n-1) (n - количество дисков).
Алгоритм
Изменим единственное условие головоломки: разрешим на первый стержень нанизать диски в произвольном порядке. Остальные правила оставим без изменений.
Перемещение дисков с первого стержня на любой другой в соответствии с этими правилами - не что иное как процесс сортировки, если интерпретировать диаметры дисков как числа.
Наилучший случай
Таковым является реверсно упорядоченный массив. Элементы сразу попадают на свои места.Соответственно наихудшим случаем является... упорядоченный массив. В этом случае мы имеем дело с каноничным "ханоем", в котором нужно произвести максимальные 2n-1 перемещений.
И вообще, чем более отсортированным является первоначальный массив, тем медленнее он будет сортироваться.
Характеристики алгоритма
| Название | Сортировка "Ханойская башня"(Tower of Hanoi sort, Hanoi sort) | |
|---|---|---|
| Автор | Эдуард Люка | |
| Класс | Эзотерические сортировки | |
| Устойчивость | Да | |
| Сравнения | Да | |
| Сложность по времени | Худшая | O(2n-1) |
| Средняя | O(exp(n)) | |
| Лучшая | O(n) | |
| Сложность по памяти | Дополнительная | O(n) |
Ссылки
Эзотерические сортировки Дэвида Морган-Мара
DM's Esoteric Programming Languages - Hanoi sort
Ханойская башня
Реализация на различных ЯП