Fastest Push_Swap Algorithm
Sorting a Stack with the least amount of moves
by Hamza Elkhatri and zainab dnaya
Push_swap it’s a Simple AI project (especially for all student that follows 42 Cursus), The Probleme solved in this project is :
We have 2 stacks, stack A and stack B, In stack A where you put the random given numbers, but for stack B at first, it’s empty until we need it in sorting.
On top of that, you are not allowed to use any moves to sort stack A, the limited moves are :
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).
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.
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.
Now! Let’s Sort it right and with the Least instructions.
Size of stack A ≤ 10.
Start with a small size of stack A per example 3 random numbers we have 5 cases and they are so obvious. stack A = [.,.,.]
case1 : [2,1,3]->sa->[1,2,3].
case2 : [3,2,1]->sa->[2,3,1]->rra->[1,2,3].
case3: [3,1,2]->ra->[1,2,3].
case4 : [1,3,2]->sa->[3,1,2]->ra->[1,2,3].
case5 : [2,3,1]->rra->[1,2,3].
we put these instructions aside!
Now we took our Stack A and we define the smallest number of the stack,
In This Case, “-62” is the smallest number. so we gonna try to push it in stack B using the moves above but to make it in fewer moves, we gonna use a new rule ( it will be applied in all cases, I mean for the size of A size A > 10).
we Gonna call it Approximity :
if we want to push an element from stack A in stack B we should put the wanted element at the top of A (then we use pb)to do that we either switch ( exp: supposedly if “-62” is after 50 in our stack A than we gonna use ( sa, pb), otherwise in our case we have to use either ( ra or rra) to know who is the fastest :
we identify the index (IDX = index) of the minimum number (-62) and then we calculate the length / 2 we put (j = lenght/2),if ( IDX >j) we use (ra) else use (rra),For example (I worked with a linked list).
To apply it in our example it gonna be faster to use (rra) since (-62) in index “6”. each time I push to B I choose a new minimum from stack A, I keep pushing into stack B until either Stack A is automatically sorted or until A have only 3 elements left.
if the 3 elements in stack A are not sorted we use the 5 case sort, the method above then we push to stack A a (pa). like this ! check the GIF below.
Size of stack A >10 && A ≤ 100
It almost the same method but we gonna do a trick here.
we will define a key_nbr, what is a key_nbr!? how !? why !?
Key_nbr: it’s our chosen number, to make sorting A easier and faster, The main idea is that we gonna define key_nbr with a very clever way in order to compare it with the numbers in stack A so we can divide stack A into chunks, from smallest to the biggest.
how: first we sort stack A as you want ( forget about the limited moves)let’s call our sorted stack A stack K (stack K will be our secret to minimum sort). then we took that stack K and we divide its size by 4 per example “we took randomly unsorted numbers from [0,100] we sort it as we want and we divide it [100 / 4 = 25]” now the number in index 25 will be our key_nbr in our example “ key_nbr = 25 “.
we get back to our initial given stack A(unsorted) and check all numbers that are under or equal to the key_nbr, and we push them in stack B ( using the move ra, rra ,sa, pb) [!! Here you should use the Approximity method that we talk about it above]. ( instead of (-62) u will look for all number ≤ key_nbr).
You will notice the smallest 25 number will be first in our stack B . so the first small quarter (1/4) is in B and 3/4 still in A.
after that in the same way, we gonna choose a key_nbr for the next quarter (2/4), To demonstrate with our simple example the next key_nbr will the index 50 which is 50 and again we took all numbers that are under 50to push them in stack B [Be cleaver and use Aproximity method ] . we keep repeating the same method until stack A has one-quarter of its initial length but stack B has the 3 quarters (3/4) of stack A.
why !? : By Chosen the correct precise key_nbr, you will notice that u will put in stack B chunks that are kind of sorted, the smallest numbers are in the bottom of stack B, then the next small chunk, then the medium …, so You will only have to sort in Stack A the last bigger numbers.
You Easily sort stack A by looking for the smallest number to put on top of stack A (Approximity Trick !), Then we Move to stack B and start Looking for the biggest number (it always will be in the last chunk you put into B so either you have cases like just swap and push(sb, pa)/or u use (rb, rb …)until u put ur wanted number on top then push, then usually u gonna use (rrb,rrb..) so the number u put down will be in top again to push them in A(rrb ,.., pa), You keep looking for the biggest number and push it in stack A until stack B is empty! ==>[Et VOILA!] automatically stack A is Sorted
You will see all of it in the Bellow, Please observe how it moves!
The visualizer GITHUB: https://github.com/o-reo/push_swap_visualizer
For : Stack A > 100! same as above.
first, we sort stack A as you want ( sorted A = stack K ). then we took that stack K and we divide its size by 8 the first key_nbr will be the number in the index [size K /8] (sidenote: size A = size K).so we get back to stack A and we look for the number are under key_nbr [Approimity trick], to push them in B, we keep doing it until we have 7/8 chunks in stack B, we sort stack A and then do the same trick to push in stack A, with the same method explained above.
I couldn’t upload the Gif of 500 number because it’s heavy but you can test 500 random numbers on my GitHub.
Note: the Chosen Numbers (4 & 8) are not randomly but we kept testing until we find the perfect number to divide Stack A to chunks.
> I Hope my explanation is clear, we are open to questions and test suggestion to know about the subject and the project you can check my GitHub :https://github.com/zainabdnaya/ ,or You can check Hamza Elkhatri Github : https://github.com/Hamzaelkhatri/push_swap
Thanks, Good Luck !
