Push_Swap Turk algorithm explained in 6 steps

Disclaimer: This article is made for people who are stuck with only algorithm left in the project. If you haven’t impelemented parsing input, data storage , operations or sort 3 numbers, go back to the project and code them untill you reach to the point you wanna start coding for the algorithm.

Background story

As a student studying Hive Helsinki , when I first started this level of the projects, I heard so many talking about how difficult push_swap is as a project, especially regarding the algorithm part.

Naturally, I am intimidated by the huge, fancy word “algorithm”. Because I first encountered it during piscine which led to a huge frustration. At that time I tried to tackle the rush_01 project by understanding the backtracking algorithm which turned out to be a rabbit hole and absorbed my brain cells 🤮.

I always like to approach a project by first doing some research about it so I took my time reading several articles (I will list them at the end of this article) and one book about algorithms (Grokking Algorithm) . Those articles are awesome but something just didn’t click for me for a long time. I spent almost a week stumbling on the algorithm part while the other parts of the project (parisng input, storage data into stack, operations) were completed a while ago.

One day, one of my peers approached me and said with confidence that he could explain the algorithm to me in 10 minutes. He used the Turk algorithm and he is Turkish. Maybe that’s why he is so good at explaining this? (Just kidding 😼). And boom, after 10 minutes, I grasped the core logic and went back to code the idea from scratch. I finished my project after 2 days of daily 10-hour coding and debugging. It’s just that fast and easy!

Shout out to my peer from Hive Helsinki that can explain complicated things very simply and easy to understand for beginners.

So without further ado, let’s dive into it.

Prerequisite

You should already have some understanding of what is stack and is able to initiate both stack a and b putting the input data into it no matter whether using pa, pb, sa, sb, etc. And one more thing, you should be able to sort only 3 numbers. It’s not that hard. I hard-coded all the permutations in my code which shocked my evaluators. It’s not elegant or smart but it works!

Step 1 pb pb pb pb …

I will give the example of 7 random numbers and use visualization because I am a visual person :)) Let’s assume I received 7 numbers from the terminal and they are stored in stack a when I first start my algorithm. You should be able to store those 7 numbers in your stack a when this happens.

./push_swap 3 7 8 4 9 2 5

The first step of the Turk algorithm (or this modified version) is to blindly push every node from stack a to stack b until there are only 3 numbers left in stack a. Why? Because we have the “sort 3 numbers” function ready!

Blindly fist push everything to stack b without any consideration

Step 2 Sort 3 numbers

In the example above the 3 numbers are not sorted, so I will use my hard-coded function (or your smarter way) to sort the 3 numbers. And now the magic will begin.

After using sort 3 numbers, stack a is in good shape.

Step 3 Find the ”target node”

What is the definition of a “target node” ? It’s called the smallest bigger. Bigger than the node in stack b but is the smallest bigger in stack a. I don’t have a very mathematical explanation of why we are doing this but my understanding is that we want to cut down the difference of sorted numbers in the stack a gradually by pushing nodes from stack b to a one by one.

To find the smallest bigger, there are 2 conditions:

• it’s bigger than the node in b
• it’s the smallest one.

Let’s take the first node on stack b number 4 as an example. To make the above condition fulfilled we can break it down:

• On stack a, both 7 and 8 are bigger than 4;
• 7 is the smallest between the 7 and 8;

so 7 is the “target node” for number 4. I will visualize it too.

But what if the node in the stack is already the biggest one? For example, number 9 in the stack b is bigger than everything in stack a. In this case, simply just push it on top of the smallest number in stack a. Putting the smallest and biggest near each other makes it easier in the last step to simply bring the smallest number on top and viola, it’s sorted.

Find target node for every number in stack b and store the node (somehow)

Step 4 Calculate “to top cost”

We can push a node from stack b to stack a by pa operation. But I want to push a specific node that I want (for example number 2) to stack a. We need to first bring number 2 to the top to stack b and push it. That’s why we need to know the “bring to top cost” of every node in stack b. We want to make sure when we push the node from b to a, it will be stored on top of the target node we have just calculated. In order to do that, we will need to make sure before we push, the target node is on top of stack a too. That’s why we need to calculate the cost for the target node.

calculate cost with the help of index number

One might wonder, how do I know if should use reverse rotate or rotate to bring the node to the top? Turk gave us a simple solution. Use the index of the nodes. If it’s in the first half of the stack (index ≤ number of nodes / 2), rotate, vice versa. And the “bring to top cost” will be the index number of the node. To put this concept into pseudocode, you can see as follows:

if (node index number <= number of nodes / 2)
  bring to top cost = node index number;
else
  bring to top cost = number of nodes - node index number;

calculate cost using index of nodes

And of course, in order to use this index number, you will have to figure out how to assign index values for the nodes in ascending order. But you can figure it out yourself. I trust in you.

Visualize the calculation logic using the chart below. One thing to mention is that even though I put “rrb * 2” to demonstrate how does “to top cost” 2 comes out, we haven’t yet operated any nodes, and no operation has been executed at this stage.

where does the “to top cost” value comes from for each of the node

Following the same manner for each node in stack b, we can now calculate the “bring to top cost” for all the nodes in stack b. See the chart below:

Calucate all the cost for all the nodes in stack b and its target node

Step 5 Find the “cheapest node”

Now we have 2 “bring to top cost”, the cost of a node in stack b and the cost of a node in stack a. Simply add them together, and that is the total cost of pushing a node from stack b to stack a. By comparing all the total cost in stack b, we now can find out which one is the cheapest.

adding the 2 “to top cost” together we got a value total cost

As we can see from the chart above, there are some same “total cost” for the nodes in b. It’s simple, just use the first one in the list to push, for example, number 4 and number 9 have the same total cost, I will just push 4 first because 4 is on top of number 9. You can also decide your own logic. This works best for me.

Step 6 Execute operations

This step is just self-explanatory, do the executions and start moving the numbers. Continuing with the example above, since we have decided number 4 will be the cheapest one, I will start to do the ra, pa operations to move the numbers. Visualization as below:

The stack become the status on the right after execute the operations.

It's not over yet…

As you can see, after executing the operations, the numbers have changed in both stacks and so do their index, their target node, and the “bring to top cost”. So we will start over from step 3 find the “target node” again and go through the whole process of calculating cost, finding the “cheapest” and executing operations. You can smartly do it by using some loops.

Last but not least, as I mentioned in step 3, if the number in stack b is bigger than every number in stack a, it will be pushed on top of the smallest number in stack a. After all the numbers in stack b have been pushed to stack a, now it’s the time to finally sort all the numbers in stack a. We can do it by finding the smallest number in stack a, and rotate (or reverse rotate) it to the top of the stack a. I don’t think this belongs to my definition of steps because it’s just sort an almost sorted list of numbers. But this is the last step to bring the unsorted list of numbers in stack a to a sorted list of numbers.

sort numbers in stack a (when stack b is empty after the loop)

The regret I had in my code

In step 4 Calculate “to top cost”, my version of implementation didn’t consider the case there I can use reverse rotate (rrr) for both or rotate for both (rr) to calculate the cost. Even though I did use them to perform the execution. This will help find some nodes that will have slightly fewer operations than the original ones. I didn’t realize this until I was writing this article. But at the end of the day, I got 98% on the evaluation score ( got 5600 operations for 500 numbers ) and I am quite happy I can understand this logic. Something I want to improve more in the project is to find out more of the whys behind everything. Now I am only in the stage of knowing how, but knowing why will be more meaningful and profound for growing a developer mindset.

I hope you find this way of explanation not too difficult to understand and please do comment if you want me to improve my writing or illustration.

Reference list:

The initial article gave me the idea of the Turk algorithm. Very well written :)

[embed]Push Swap — A journey to find most efficient sorting algorithm A sorting algorithm for the push_swap project of 42 Programming Schoolmedium.com

This article introduced the concept of chunks. It’s really amazing but I failed to get the idea and changed my way to Turk Algorithm later.

[embed]Push_Swap: The least amount of moves with two stacks When I first became an official student at 42 Silicon Valley, I knew early on that I wanted to tackle some of the…medium.com

An algorithm book uses a lot of illustrations to explain things. Good for muggles like me to get started with data structure and algorithms.

[embed]Grokking Algorithms In this fully illustrated, friendly guide you'll discover how to apply common algorithms to the practical problems you…www.manning.com