Two Stacks, One Goal: Understanding the Push Swap Algorithm

The Push Swap project is a unique and challenging approach to sorting that is part of the 42 School curriculum. The goal of the project is to sort an array of integers using only a very limited set of commands. You can find the code and an explanation on how to use the program in my GitHub repository.

Let’s start with a little background: the algorithm is composed of two stacks, named a and b. Stack a initially contains a random number of positive or negative integers without any duplicates, and stack b is empty. The goal is to sort the numbers in stack a in ascending order.

Here are the available commands that the program is limited to in order to sort the numbers:

  Command |                          Description                          
 ---------|--------------------------------------------------------------- 
  pa      | push the first element of stack b to the top of stack a.      
  pb      | push the first element of stack a to the top of stack b.      
  sa      | swap the first two elements of the stack a.                   
  sb      | swap the first two elements of the stack b.                   
  ss      | swap a and b                                                  
  ra      | rotate the stack a, move the first element to the bottom.     
  rb      | rotate the stack b, move the first element to the bottom.     
  rr      | rotate both stacks                                            
  rra     | reverse rotate the stack a, move the last element to the top. 
  rrb     | reverse rotate the stack b, move the last element to the top. 
  rrr     | reverse rotate both stacks

Now, before we dive into the nitty-gritty details, it’s important to note that this algorithm is not necessarily the fastest way to sort an array. But, the goal is to use the least amount of commands possible, meaning less commands may also mean more processing time because we can look into the list as much as we want.

Well, now that we know that, let’s take a look at the steps I used to successfully sort an array using the Push Swap algorithm. Keep in mind that this is my personal approach and there may be millions of other ways to accomplish this task.

First part

Step 1: Input Validation

Before diving into sorting the numbers, I first perform a check to make sure the input is valid. This includes verifying that the input is composed of numbers only, that there are no repeating values, and that the numbers fall within the range of INT_MIN and INT_MAX.

Step 2: Initialize Stack A and Fill Values

After validating the input, the algorithm initializes stack a and fills it with the values. To optimize the sorting process, I use linked lists, where each node includes the value, the index, and a pointer to the next node.

One feature of this algorithm is the utilization of a function to map and convert the input values to consecutive numbers. This improves the algorithm’s performance when the input values are not already in consecutive order.

Step 3: Check for Sorted Input

After stack a has been filled, the algorithm checks if it is already sorted. If it is, the program exits as no further sorting is needed.

Step 4

If the length of stack a is 3, the algorithm calls a separate function, sort_three, to handle these small inputs. Otherwise all other cases are sent to the main sorting function

Sorting large inputs

Now things start to get interesting. For larger inputs I call my sort_big function to handle these cases efficiently.

Step 1: Filling Stack B

I begin by transferring values from stack a to stack b. To do this, I calculate a ratio based on the length of the list. For example, if the list is 100 elements long, the ratio would be 14. Next, I calculate the ceiling value, which will be used later in the process. This value is determined by taking the smallest value in stack a and adding (ratio * 2) to it.

To efficiently transfer values from stack a to stack b, I utilize a method of searching for the first and last values in the list that are smaller than the ceiling value. It is important to minimize the number of commands used during this process, so I carefully consider the optimal move to make each time. For instance, if the first matching value is closer to the beginning of stack a than the last matching value is close to the end, I will rotate stack a to bring the first value to the top. On the other hand, if the last matching value is closer to the end than the first matching value is close to the beginning, I will reverse rotate stack a to bring the last value to the top.

I repeat this process of searching for the optimal move and transferring values to stack b until stack a only contains the three largest values.

In the animation above, you can see how the algorithm works. The algorithm sets its value higher whenever it does not find any matches under it in stack a (by incrementing the ceiling value by two times the ratio). The reason for this optimization is to reduce the number of rotations needed. Instead of searching for two separate chunks in stack a, the algorithm searches for two at a time, and when they are transferred to stack b, they are automatically sorted.

For example, if the value is smaller than ceiling - ratio, the stack is rotated and the value is sent to the end of stack b. This is why stack b takes on the distinct shape of two triangles. The middle of the stack b now contains the smallest values, and the values increase as you move towards the edges.

Step 2: Sorting what is left in a

So this step is fairly simple, I just call my sort_three function to sort the three biggest numbers in a.

Step 3: Push everything back!

With the values in stack b “pre-sorted”, the final step is to transfer them back to stack a and complete the sorting process!

Time to push everything back to a!

To further optimize performance, I use a technique of temporarily storing values in the bottom portion of stack a. When the value at the top of stack b is not the next value in the sorted sequence and is larger than the last value stored in the bottom of stack a, it is temporarily stored there.

This allows for efficient placement of the value in its correct position in the final sorted sequence. When the value is ready to be placed, it is transferred back to the beginning of stack a.

In the case that none of these conditions are met, the highest value in stack b is searched for and sent to stack a. This approach helps to minimize the number of rotation commands used and ultimately speeds up the entire sorting process.

And that’s it! The array is now sorted in ascending order using the Push Swap algorithm.

In conclusion, the Push Swap algorithm is a unique and challenging approach to sorting that requires a bit of creativity and problem-solving skills. It may not be the fastest way to sort an array, but it is an excellent exercise in understanding how different sorting algorithms work and how to optimize their performance.

I hope this article has provided you with a better understanding of the Push Swap algorithm and how to implement it in your own projects.