Главная » Хабрахабр » Сортировка «Ханойская башня»

Сортировка «Ханойская башня»

Ханойские башни
Про знаменитую игру Эдуарда Люка́ на Хабре не писа́л только ленивый. Кажется, все покровы сорваны и что-то ещё по поводу алгоритма добавить уже невозможно. Но нет, у данной темы есть ещё скрытые ресурсы. Сегодня, в частности, мы переделаем алгоритм решения этой головоломки в полноценную сортировку. (Зачем? Just for fun. В пятницу можно.)

Псевдокод ниже по тексту — его авторства. Данный пост посвящается памяти истинного гуру программирования Андрея Mrrl Астрелина, который когда-то мне просто и доходчиво объяснил этот алгоритм.

Но мы разрешим им быть нанизанными в любом порядке.
В классической головоломке изначально диски на первом шесте уже упорядочены.

Не будем цепляться за это ограничение и разрешим повторы. Кроме того, размеры дисков предполагаются уникальными.

Если позволить себе только эти две вольности, то начальные условия головоломки можно интерпретировать как массив (диски — это числа), а задача сводится к тому, что данный массив требуется отсортировать.

Остальные условия мы (почти) не меняем:

  • У нас два вспомогательных шеста (пара пустых массивов).
  • Можем переносить диски по одному.
  • Класть только меньшие на бо́льшие (раз мы разрешили одинаковые размеры дисков, то также можно класть перемещаемый диск сверху на другие такого же размера).
  • Имеем право сравнивать переносимый диск только с самым верхними дисками (то бишь, все 3 массива являются стеками).

Наша задача: взять классический рекурсивный алгоритм головоломки…

def hanoi(n, source, helper, target): if n > 0: hanoi(n - 1, source, target, helper) if source: target.append(source.pop()) hanoi(n - 1, helper, source, target)

… и превратить его в сортировку!

По большому счёту задача решаема всё тем же классическим рекурсивным способом. На самом деле, от того что мы разрешили начальную неупорядоченность и повторы для размеров дисков — от этого принципиально не поменялось ничего. Самое главное что нужно понять — все перемещения дисков разделяются на несколько этапов, каждый из которых — это классичекий «ханой» в миниатюре.

Отсортировав по классике это небольшое множество мы приблизим общее состояние системы к классической головоломке. То есть мы на каждом этапе рассматриваем не все имеющиеся диски, а только совокупность тех из них, которые удовлетворяют старым условиям. И это множество будет бо́льшим, чем на предыдущем шаге! Тогда мы опять берём то множество дисков, которое соответствует классике и применяем известный алгоритм вновь. И так повторяем до тех пор, пока все диски на всех шестах вдруг не станут отличаться от классического состояния.

Нарушенная изначально система (тем, что на входе диски не упорядочены) самовосстанавливается с каждой итерацией.

Потому что подряд идущие одинаковые диски мы просто перемещаем как один диск. Что касается разрешения повторов, то это вообще не имеет никакого значения.

Алгоритм

Назовем столбики A, B, C (A в начале непустой).

Введем операции:

Если столбик пуст, то этот размер = MaxInt.
В->С(К) — переложить с В на С все диски, размер которых меньше К (мы это можем сделать, если верхние диски А и С не меньше К).
swap() — переставить столбики В и С (или переименовать их — нам ведь все равно, где окажутся диски).
while(A) — цикл пока А не пуст. А->С() — переложить один диск с А на С.
top(A), top(С) — размер верхнего диска А или С.

Тогда работает такой алгоритм:

//С каждым перемещённым диском с шеста A всё более восстанавливаем "ханойскую" систему
while(A) A->C();
} //Система восстановлена. Завершение - классический "ханой"
while(C) { B->C(top(C)); swap();
}

© Mrrl

Сложность

В худшем случае сортировка стремится к сложности по времени для классического алгоритма, который хоть прост и изящен, но при этом максимально неэффективен. Насчёт лучшей и средней предположить затрудняюсь.

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

Реализация

Свой вариант на Python пока не написал (сделаю это позже). Однако ниже в разделе «Ссылки» накидал несколько ссылок, по которым можно посмотреть имплементации на различных языках. Особенно интересен вариант на Джаве. Автор не стал брать за основу общеизвестный рекурсивный способ для решения головоломки, а построил кратчайшее дерево путей. Предположительно, это является самым эффективным решением, если писать сортировку в стиле «Ханойской башни».

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

Название

Сортировка «Ханойская башня», Tower of Hanoi sort

Автор идеи

Эдуард Люка́

Класс

Сортировки вставками

Сравнения

Есть

Временна́я сложность

лучшая

?

средняя

?

худшая

O(2n)

Ссылки

Tower of Hanoi / Ханойская башня

Реализации: Си, Java vs C++ vs Python, Python.

Статьи серии:

В приложении AlgoLab данная сортировка теперь доступна. Хотя она относится к классу сортировок вставками, по причине экстравагантности алгоритма она помещена в раздел «Прочие сортировки». Ещё там есть ограничение — числа в сортируемом массиве могут быть только от 1 до 5 (связано с непростой прорисовкой дисков). Другие числа всё равно будут заменены на эти.

Сделано это сугубо в Ваших же интересах — если возьмёте слишком большой массив, то, может так статься, что сортировать его придётся до глубокой старости. Также есть ограничение на размер массива — не более 20-ти элементов.

EDISON Software - web-development
Статья написана при поддержке компании EDISON Software, которая профессионально разрабатывает умное городское освещение и поддерживает сайты на питоне


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Иди-ка ты сам на… или правила общения в команде

Пост-ответ на статью "Иди-ка ты на !@# со своей "токсичностью"". Если бы я последовал советам из этой статьи, мне достаточно было бы проявить эмоцию и сказать автору "Иди-ка ты сам на на ..., ты ничего не понимаешь!". Поэтому давайте разберем ...

[Перевод] Сделал редизайн — потерял миллиард

Исследуем эпичные провалы редизайна и мотаем на ус. Менеджер по продукту заходит в отдел дизайна и заказывает редизайн сайта. «Наш сайт выглядит таким старым! У всех наших конкурентов есть более яркие сайты. Давайте перепроектируем его. Кнопки с разноцветными тенями — ...