Sort "Tower of Hanoi"

^{Hanoi Towers}
About the famous game of Edward Luke on Habré did not write just lazy . It seems that all covers have been torn off and it is already impossible to add something else about the algorithm. But no, this topic has more hidden resources. Today, in particular, we will remake the algorithm for solving this puzzle into a complete sorting. (Why? Just for fun. On Friday, you can.)

This post is dedicated to the memory of the true programming guru Andrei Mrrl Astrelin, who once explained this algorithm to me simply and intelligibly. The pseudocode below is its authorship.


In the classic puzzle, initially the discs on the first pole are already ordered. But we will allow them to be strung in any order.
')
In addition, disk sizes are assumed to be unique. We will not cling to this restriction and allow repetitions.

If you allow yourself only these two liberties, then the initial conditions of the puzzle can be interpreted as an array (the disks are numbers), and the task boils down to the need to sort the given array.

The rest of the conditions we (almost) do not change:

• We have two auxiliary poles (a pair of empty arrays).
• We can transfer discs one by one.
• Put only smaller ones for the most part (since we have resolved the same sizes of the disks, it is also possible to put the movable disk on top of others on the same size).
• We have the right to compare the portable disk only with the uppermost disks (that is, all 3 arrays are stacks).

Our task: to take the classic recursive puzzle algorithm ...

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) 

... and turn it into a sort!

Actually, from the fact that we resolved the initial disorder and repetitions for the sizes of the disks - nothing fundamentally changed from this. By and large, the problem is solved in the same classical recursive way. The most important thing to understand is that all movements of the disks are divided into several stages, each of which is a classic “khan” in miniature.

That is, at each stage we do not consider all the available disks, but only the totality of those that meet the old conditions. Having sorted this small set according to the classics, we will bring the overall state of the system closer to the classic puzzle. Then we again take that set of disks which corresponds to the classics and apply the known algorithm again. And this set will be larger than in the previous step! And so we repeat until all the disks on all the poles suddenly begin to differ from the classical state.

The system that was initially broken (by the fact that the disks are not ordered at the input) self-restores with each iteration.

As for the resolution of repetitions, it does not matter at all. Because we are moving identical discs in succession just as one disc.

Algorithm

Let us call the columns A , B , C ( A at the beginning is non-empty).

We introduce operations:

A -> C () - shift one disk from A to C.
top (A) , top (C) - the size of the upper disk A or C. If the column is empty, then this size = MaxInt .
B -> C ( K ) - shift from B to C all disks whose size is less than K (we can do this if the upper disks A and C are not less than K ).
swap () - rearrange columns B and C (or rename them - we do not care where the disks will be).
while ( A ) is a loop while A is not empty.

Then this algorithm works:

 //      A    ""  while(A) { K = top(A); //-""    while(top(C) < K){ B->C(top(C)); swap(); } A->C(); } // .  -  "" while(C) { B->C(top(C)); swap(); } 

© Mrrl

Complexity

In the worst case, the sorting tends to time complexity for the classical algorithm, which is simple and elegant, but at the same time as ineffective as possible. About the best and average difficult to guess.

As for memory, we can say that if recursion is used, then the costs will be appropriate.

Implementation

I haven’t written my own version of Python yet (I’ll do this later). However, below in the "Links" section I have added a few links on which you can see the implementation in different languages. Particularly interesting option on Java. The author did not use the well-known recursive method for solving a puzzle as a basis, but built the shortest path tree. Presumably, this is the most effective solution if you write sorting in the style of the “Tower of Hanoi”.

Algorithm Characteristics

Title	Sort “Tower of Hanoi”, Tower of Hanoi sort
Idea author	Edward Luke
Class	Sorting inserts
Comparisons	there is
Time complexity	the best	?
	average	?
	the worst	O ( 2 n )

Links

Tower of Hanoi / Hanoi Tower

Implementations: C , Java vs C ++ vs Python , Python .

Articles series:

• Excel application AlgoLab.xlsm
• Exchange sorting
• Sorting inserts
  • Librarian sort
  • Solitaire sorting
  • Sort "Tower of Hanoi"
  • Sort by Young table
  • Inversion Sort
  • Comparing sorting inserts
• Sort by selection
• Merge sort

In the AlgoLab application, this sorting is now available. Although it belongs to the class of sorting inserts, because of the extravagance of the algorithm, it is placed in the “Other sorting” section. There is also a limit - the numbers in the sorted array can only be from 1 to 5 (due to the difficult drawing of disks). Other numbers will still be replaced by these.

There is also a limit on the size of the array - no more than 20 elements. This is done purely in your own interests - if you take too large an array, then it may be that you have to sort it to a very old age.

The article was written with the support of the EDISON Software company, which professionally develops smart urban lighting and supports python sites.