Home
Push_swap is an algorithm project at school 42. I’ve passed with a full score of 125/125 and I’ll try to explain how I’ve solved it.
I recommend you to read this article and apply my algorithm only if you are as lazy as I am, 😂. (I was way too much lazy to break down the other complicated solutions such as Redux sort.)
As a 42-Heilbronn student, I always search for some resources or blog posts when I start off a new project. Because I like to start my projects with reading some brief summaries. I’ve read some blog posts about push swap project. One of them was suggesting to use **Radix Sort** while **another one** was suggesting to divide stacks in some little chunks. But I was looking for something more straight forward which will bring me 125 out of 125.
By the way, if you are wondering what is push swap project and what are the rules, there are enough resources on the web. You can ***click here*** to read the subject and rules. If you don’t know the topic and rules, you better read it first.
You start with two empty stacks: a and b. You are given a random list of integers via command line arguments.
Only these moves are allowed:
-
sa : swap a - swap the first 2 elements at the top of stack a. Do nothing if there is only one or no elements).
-
sb : swap b - swap the first 2 elements at the top of stack b. Do nothing if there is only one or no elements).
-
ss : sa and sb at the same time.
-
pa : push a - take the first element at the top of b and put it at the top of a. Do nothing if b is empty.
-
pb : push b - take the first element at the top of a and put it at the top of b. Do nothing if a is empty.
-
ra : rotate a - shift up all elements of stack a by 1. The first element becomes the last one.
-
rb : rotate b - shift up all elements of stack b by 1. The first element becomes the last one.
-
rr : ra and rb at the same time.
-
rra : reverse rotate a - shift down all elements of stack a by 1. The last element becomes the first one.
-
rrb : reverse rotate b - shift down all elements of stack b by 1. The last element becomes the first one.
-
rrr : rra and rrb at the same time.
At the end, stack b must empty empty and all integers must be in stack a, sorted in ascending order.
Nothing special. Let’s call it the Turk Algorithm. Not because of I am Turkish but because of the Mechanical Turk story. I will call it like that because this algorithm is hard coded and it is not elegant. Likewise Mechanical Turk, lol. Okay I better not to divert the subject.
First of all, it’s important to mention that I will walk thorough without explaining any code. But, you can **click here** to go my repository and check my code to understand things better.
Let me start with mentioning some ground rules.
— I slowly push everything from STACK_A to STACK_B but in descending order. Why? Because after I push them back to STACK_A, they will be automatically sorted.
— Stacks are kind of circular linked list. It means, the last element of the stack is actually not the last element. It is actually an element before the first element.
— If the number you push from STACK_A to STACK_B is going to be the new biggest or the smallest number, you should place it just above the old biggest number in the STACK_B.
If we were going to push the number “9” instead of the number “1”, you can see that correct position of the number “9” is again would be the right above the number “4” in STACK_B. The number “4” is the MAXIMUM number of the STACK_B. So, I think you can see now what I’m saying. If the the pushing number is neither MAXIMUM nor MINIMUM, it should be somewhere inside the STACK_B. We have to find it manually.
— The magic number is 3. If your stack size is three, you should understand one thing. When you have a stack in size of three, it means you don’t need to push something or overcomplicate the things. Because if the stack size is three, you only need one operation to sort the stack. (Except one case which is a descending sorted stack such as 3–2–1. It would require two operations) So remember this magic number.
— We should be vigilant. So, let’s imagine that we should rotate three times STACK_A and four times STACK_B. Basic math tells us, 4+3 equals to 7. It makes seven operations. This is why we will do a walk around solution. We will choose the least common number among these amount of rotations. So, instead of doing four times A rotate and three times B rotate, we can do three times rotating together. After that, if we rotate STACK_B one more time, we will get the desired result. But this time 3+1 will be 4 operations we did. Instead of doing 7 operations, we did 4 operations. Pretty efficient. This is why we will always calculate before rotation.
Okay, I create a small stack with 10 members for you guys. And let us sort this stack with my algorithm.
As I mentioned previously, in order to determine a number’s correct position in STACK_B, I need a maximum number in STACK_B. If the number I am pushing is neither MAXIMUM nor MINIMUM, the number have to be somewhere else inside the STACK_B. Hence, my algorithm starts with pushing two numbers from the top of the STACK_A to the STACK_B without checking anything.
After that certain point, now we will count all the time. We will count and calculate for every numbers one by one before every each push. We will calculate how many operations would it take to push the number into correct position in the STACK_B. Let’s start the calculations…
-
7 : We need to rotate STACK_B and then push it(Because 7 is going to be the biggest number in the STACK_B and this is why it should be placed above the current maximum number in the STACK_B which is 5. But number “5” is down below so this is why first we should rotate the STACK_B to bring the number “5” to the top. After I rotated, now I can push the number “7”). So it requires 2 operations. If we cannot find another number which requires less than 2 operations, we will push that number. Otherwise, we will push the number “7”.
-
1: We need to rotate STACK_B and STACK_A then push it. 1 time STACK_A rotation, 1 time STACK_B rotation, and then push the number to the STACK_B. It was “3” operations. If you remember the basic math I’ve explained previously, you can rotate two stacks at the same time. By this way instead of “3” operations, you could do “2” operations. But still it is not less than previous time. Still our champion is number “7”.
-
6: The number “6” will be the biggest number in STACK_B. So you can do the same logic like in first step. You will see that it would take “3” operations to put the number “6” in correct position in STACK_B.
-
3: This little friend needs “4” operations to put him in correct position. Still it isn’t cheaper.
No need to continue this. You can see that, cheapest number is “7”. So, let us push him.
Again start calculations one by one for each numbers in the STACK_A, and find the cheapest number. Well… The cheapest one is the number “1”. Because it is visible that it it requires only and only one operation. No need to check rest of the stack. We already found the cheapest number. So, let’s quickly push him into STACK_B.
Let’s start calculation again.
-
6: It should be just above the number 5. It requires two times rotation of STACK_B and one push from A to B. Which means “3” operations are required.
-
3: It should be just above the number “2”. It requires one rotation of A, one reverse rotation of B and and one push form A to B. If we do rotations at the same time we can count them as one operation. So one rotation of A and B and one push. This would be “2” operations. Oh! We have a new winner. The cheapest number is number “3” for now.
You can continue to calculate each numbers till the end but you cannot find any other cheaper number. So, our winner is number three. Let’s push him.
Okay, one last time we will do our classic calculations. Yes, last time. Why? I will explain. Stay tuned. So, let’s dive into calculation:
-
9: Two times STACK_B rotation and push operation. It would be three operations.
-
4: One time STACK_A rotation and push operation. It would be two operations. We have a new winner.
-
8: It requires three operations.
-
6: It requires two operations.
It seems like the number “4” and the number “6” need two operations. But in my algorithm, I was choosing a cheapest number and I don’t change this if I can’t find a cheaper one. So, after I chose the number “4”, my decision doesn’t change with the number “6”. Because it is not cheaper than the number “4”. Thus, I will push the number “4”. Let us do it.
Do you remember I’ve mentioned above the importance of three. Yup. This is the reason. This is why we stop at this point. We don’t need to push the numbers to the STACK_B anymore. Because we can sort these three numbers only with one operation. In worst case, it would be only two operations. Okay, in our case this is the worst possible scenario that we could get. LOL.
We have to do two times reverse rotation in STACK_A. After these two rotations, STACK_A will be sorted. And it will look like this:
In this stage, we push everything from STACK_A to the STACK_B. With one simple exception. Every time before we push a number, we check if it is being pushed to the correct position. If it is not, we rotate STACK_A until correct position come up. Let’s see how it is being executed.
Now we will push the number “7”. In order to push it to the correct position, we have to reverse rotate the STACK_A two times. Because seven should be placed right above the number eight. So two times rotation and one time push. After that, it will look like this:
The final number which is “5” should be right above the “6”. So we should do a reverse rotate in STACK_A and then we should do the push. So it will look like this after operation:
We are almost done. In final step, we do one simple thing. We should bring the minimum number of the stack to the top of the stack. It means the number “1” should be placed on the top of the STACK_A. So, it means 4 times reverse rotation. After that your stack will be sorted.
And here we are. You sorted the stack. If you understand the logic behind and code this algorithm, you will get full score from the project which is 125/125. I hope you are satisfied and it is clear enough. I was hoping to answer the questions such as “How to do push swap project?” or “Which algorithm is better for push swap?”. I think there are plenty of answers to those questions. And I only answered based on my experience. As a 42 student with peer to peer learning spirit owner, I learn a lot from community and I hope to give it back. I hope you will do the same after you got from me. Good luck with curriculum :)