Сортировка "Ханойская башня" :: 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

Ханойская башня

Реализация на различных ЯП