Not your typical 42Network push_swap algorithm
Push_swap is a sorting algorithm problem that 42 network students must tackle on their way through the school curriculum.
Briefly, This project is as follows.
You have to sort a stack using the least amount of instructions(no more than 5500 to be considered perfect), and On top of that, the only way you can manipulate data in the stack is with a limited set of instructions.
In the beginning, the path was not as clear, but after collaborating with my peers in school, the road became more fun and enjoyable. Therefore in this article, I would like to share this experience and the rollercoaster of breakthroughs with you.
For the record, I did not make everything from scratch. On the contrary, I optimized and changed some stuff in the base algorithm. But I wouldn’t have been able to reach what I achieved during the same time frame without all the helpful suggestions I got from my close friends hamza hoummadi and iman rhesri. I am very grateful for the inspiring ideas proposed by both of them.
PS: I will explain the algorithm’s logic in this article and leave the rest of the implementation to you.
PS: here is a tester that should help you debug the algorithm and a visualizer that will make your life much easier:
tester: https://github.com/mohamed-souiyeh/push_swap_tester
visualizer: https://github.com/o-reo/push_swap_visualizer
Instructions Description :
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: equivalent to as and sb combined.
pa: push a — take the first element at the top of b and put it at the top of a. Do nothing if stack 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 stack 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: equivalent to ra and rb combined.
rra: reverse rotate stack a — shift down all elements of stack a by 1. The last element becomes the first one.
rrb: reverse rotate stack b — shift down all elements of stack b by 1. The last element becomes the first one.
rrr: equivalent to rra and rrb combined.
The overall algorithm consists of two main stages :
first: Pushing numbers from a to b.
second: Pushing them back to a.
the first stage from stack a -> b:
The basis of this stage is to transfer chunks as efficiently as possible to smooth things for the next part of the algorithm.
The first step is storing the stack in a new array using any sorting algorithm for reference.
and then initialize the following variables:
n: is a constant that is set depending on the size of the stack, and it helps in calculating the offset (or chunk size), for 10 numbers or less n = 5, for 150 or less n = 8, and more than 150 n = 18. these numbers are just starting points; you can calibrate them to the performance you prefer.
middle: as the name suggests, this is the middle of the sorted array(stack size / 2).
offset: this variable is the chunk size, which equals (stack size / n).
start: this is the start of the range that will be pushed, it is an index in the sorted array (middle - offset).
end: this is the end of the range that will be pushed, it is an index in the sorted array(middle + offset).
After initializing the variables: n, offset, middle (which shouldn’t change during the rest of the execution), start, and end, we have to transfer a chunk at a time starting from the start index to the end index of the reference array, then after moving a whole chunk update those indexes.
Every chunk processing is as follows: if the number belongs to the chunk (between start and end), then push it to stack b. now we should check if the number we pushed belongs to the interval under the middle. If so, then rotate it. So technically, the chunk we are pushing is treated as two chunks separated by the middle index in stack b.
After transferring all the numbers belonging to a chunk, we have to update to a new range, and that is by adding the offset to the end index and subtracting the offset from the start index, in the reference array.
This technique will make the chunks in the stack sorted from the ones with the most significant numbers to the least significant numbers, and the overall stack kind of sorted.
The second stage from stack b -> a:
All the magic happens In this stage because instead of taking the most significant number at that point of time and pushing it until stack b is empty. we are going to take as much as we can to stack a in our way to make the most significant number at that point of time the head of the stack b.
We will achieve that by using the space at the bottom of stack a, don’t freak out. Let me explain. Instead of rotating and reverse rotating some numbers in stack b, we can put them at the bottom of stack a in ascending order so they can stay there until we don’t find the needed number in stack b. We reverse rotate the stack a, and tadaa 🎉 it’s right where it needs to be.
The trick is in the condition that push numbers to the tail of stack a. Let’s see how it works.
we need a variable to keep track of how many numbers we have at the bottom of the stack a let’s call it “down”, so if the down is empty, aka equal 0, or the number in the head of stack b is bigger than the number in the tail of stack a than we can push the number in the head of stack b to stack a and rotate it to put it in the bottom of the stack a, the pseudo-code would be as follow :
Do the following while the stack b has numbers in it or down contain some numbers:
— search in stack b for the biggest number to be pushed in its appropriate place in stack a and return its index; If not found, return -1.
— If the number we are searching for is present in stack b, then do the following:
check the head of stack b; if the desired value is there, then push it to stack a; if not, then check if the variable down == 0 or the head of stack b > the tail of stack a; if true, then push and rotate, if false than based on its index you can decide whether you rotate or reverse rotate your way to it.
And that’s it for the base algorithm. It averages between 4700 to 5100 instructions which are less than the threshold set(aka 5500 instructions), but in the following part, the exciting stuff starts. We will look at the optimizations I added to it to reach 3700 as a min value and 4300 as the worst case, and I will give it some time in the future to make it even better while maintaining the same time and space complexity.
optimizations
— The first optimization I added was in the first stage (from a -> b), so instead of waiting until I finished transferring both the upper chunk and the lower chunk and then updating the start and end, I separated them and updated each one of them the moment its corresponding chunk got transferred.
— The second one was pretty minor; it was just leaving the biggest 3 numbers in stack a and sorting them with the algorithm that sorts 3 numbers in max two instructions (i didn’t cover it here because I thought it’s too easy to be mentioned).
— The third optimization was to use the upper area of stack a before getting the appropriate number there to make full use of the down area of stack a, because if the second big number got directly to the down area, no other number smaller than it can get in there.
So instead of pushing it to stack a and rotating it right away, I push it and record that in a variable called “up”, and in the way, if I find the number in the head of stack b that is smaller than the number in the head of the stack a (up area), I push it to stack a. If I find a number in the head of stack b that is in some place between the upper numbers, I rotate until I reach a number bigger than it, or I get the upper area empty and then push the number there. If I find the actual searched number, I leave one number in the upper area and then push it and swap it in its appropriate place; all of this is managed automatically with this pseudo code :
The following routine will be repeated as long as there is a number in stack b or the upper area or the down area:
search for the current biggest number that needs to be pushed to its proper place; if the number is not found then check the head of stack a if the number is there then decrement the variable that tracks the upper side of stack a else reverse rotate stack a and decrement the variable that tracks the lower side of the stack a, but if the number is present in stack b then check if the head of stack b can be pushed to the down area in stack a(same condition as the base algorithm) after evaluating that rotate stack a as long as the head of stack a is smaller than the head of stack b and the upper area of stack a contain numbers and than push it after the last loop break and don’t forget to keep track of the upper and bottom area variables, increment and decrement them when needed. Lastly, if the desired number is in the head of stack b, rotate stack a until you are left with one number in the upper room, then push the number to stack a and swap it to its appropriate place.
— Last but not least, the final optimization is in the printing part of the algorithm. Making full use of the rrr and rr and ss instructions and not printing the instructions that negate each other will surprise you with how much instruction will save. I achieved that by desynchronizing the printed instruction with the executed instruction at that moment. So basically, I store the first instruction that comes in a static string pointer and then compares it with the following instruction that comes in; then, I reduce them to one(in the case of ra and rb are equal to rr) and free the static variable, if I cant reduce them then I print the old one and store the new one in the static variable. If the instructions negate each other, then I free the static variable without printing anything. and in the very last thing in my code, I call the printing function with an empty string to print any leftover instruction in the static variable.
These are the optimizations that I added to the base algorithm to make it on steroids, and I think with the right set of skills, it can be even more pushed and optimized and made better. Thank you for reading. I hope this humble article helped even a little. Good luck with your projects, and goodbye.
