How to Over-optimize an Algorithm : Push_Swap (42 School Project)

I recently began my studies at 42 School (Paris). Before joining this program, my experience was mostly limited to creating a few projects, such as small websites or bots in Python. Naturally, transitioning to programming in C has been significantly more challenging.

One of the very first projects you can unlock at 42 is Push_Swap, and that’s what we will discuss here. But first, let me explain the concept of the project : You are given two stacks, A and B. Stack A contains a random list of integers ranging from INT_MIN (-2³¹) to INT_MAX (2³¹-1). Stack B, on the other hand, is initially empty. The objective is to sort Stack A in the most efficient way possible.

However, you’re limited to a specific set of moves: sa, sb, ss, ra, rb, rr, rra, rrb, rr, pa and pb. Here’s how each of these moves works:

How each moves works.

Now that you understand the project, let’s move to the resolution :

First, you need to handle the case where fewer than six numbers are given in stack A. Why ? Because while it’s possible to optimize an algorithm for large datasets and another for small datasets, creating a single algorithm that efficiently handles both is significantly more challenging.

Nevertheless, I won’t explain how to handle cases with only a few numbers, and for one very important reason: it’s really, like… really simple.

So, let’s move on to the main part of the project: the algorithm for handling large numbers. We will focus on two cases for this algorithm: sorting 100 numbers and 500 numbers. Why these specific cases? Because, according to the project instructions, you must sort 100 numbers in fewer than 700 operations (where one operation equals one sa, rb, etc.) and 500 numbers in fewer than 5,500 operations. Simple? Right? Well, not exactly.

100 random numbers:

When I first started thinking about how to sort 100 numbers, I considered using a radix sort or a greedy algorithm. However, the radix sort turned out to be inefficient, and the greedy algorithm was too slow for the computer to complete. I ended up wasting about twenty hours of coding time, trying to implement a radix sort that met the 100-number condition (fewer than 700 operations), but still failed the 500 numbers. So, instead of passing an 80/100 grade, I aimed for a perfect score and eventually used a merge sort algorithm — more specifically, a chunk sort algorithm — instead.

Here’s how I proceed :

1- Calculate the gap between the minimum and the maximum values of stack A. 2- Divide this gap in three chunks. The division makes it more efficient to perform an insertion sort later on. 3- Traverse stack A, and whenever I find a number within one of the current chunk, I push it into stack B using the pb operation. 4- If the number I just pushed from Stack A falls into the lower half of the chunk range, I move it to the bottom of Stack B using the rb operation. 5- Repeat this process until Stack A is empty.

By doing this, I end up with Stack B containing numbers that are already somewhat sorted. Now, it requires fewer moves (operations) to sort Stack B back into Stack A. Here’s a visualizer for the first part (with Stack A on the left and Stack B on the right):

Visualizer of the first part

I now have a partially sorted Stack B, and it’s time to push it back into Stack A, but this time fully sorted. Initially, I simply pushed back the maximum of Stack B into Stack A. However, I quickly realized this wasn’t optimized enough for our project. Here’s how I improved it:

1- First, I push the two largest numbers from Stack B into Stack A. 2- Then, for the rest of my Stack B, I proceed conditionally :

• If the number currently on top of Stack B isn’t the maximum, but the maximum is too far away (more than two moves), I push the current number onto Stack A and perform a ra to move it to the bottom of Stack A.
• I repeat this for each number. However, the new number must be larger than the element at the bottom of Stack A; otherwise, it would be too difficult to sort later (if the number is smaller, I take the best path to go to the maximum of Stack B, and I check if the previous condition after each move).
• When the number at the bottom of Stack A is greater than the current maximum of Stack B, I simply push it back to the top of Stack A using a rra.

With this strategy, I’m able to sort the pre-sorted Stack B into Stack A. Here’s a visualizer for this part:

Visualizer of the second part

Now that we have an efficient algorithm for sorting 100 numbers, do we need to create an entirely new algorithm for 500 numbers?

500 random numbers:

When I started to think about this question, I first tried my current algorithm on 500 numbers. Honestly, not my best idea… so many operations were required to sort it correctly.

Then, I decided to experiment with a different approach. Instead of dividing the data into 3 chunks — because that was the optimal number for sorting — I tried using 20, 10, and eventually settled on 8 chunks. What a great idea ! Now, with exactly the same algorithm, I can sort 500 numbers with an average of 4,900 operations — 600 fewer than the required limit!

One last time, here is the visualizer of 500 numbers:

Visualizer of the algorithm on 500 numbers

Few tips to optimize your code:

You can already guess that, with this type of project, optimization is the “best” part. Here are few tips to help you complete the project:

• Maximize the use of rr and rrroperations. You can save a lot of operations by using these two moves strategically. The best way to optimize your code with is to implement a “wait-for-condition function”.
• Update the size of your chunks in real time. For example, your first chunk can be twice as large as your second. This approach helps reduce the number of moves needed to sort the numbers in Stack A.
• Customize your algorithm as much as possible. Don’t settle for a simple merge sort. The goal is to learn how to develop your own sorting algorithm and apply innovative strategies to meet the project’s requirements.

Let’s conclude

Of course, because it’s a 42 School project, we aim for the best possible result. That’s why I’m continually optimizing this algorithm. As of now, my current scores are:

• An average of 590 operations for sorting 100 numbers.
• An average of 4,900 operations for sorting 500 numbers.

I also didn’t explain some parts of the project, as I wanted to focus this article solely on the algorithm itself. However, we had to parse the list to check if it contains valid numbers within the range fromINT_MIN to INT_MAX. I also developed a checker to verify if the list is correctly sorted and a tester (in a shell script) to automatically test the program multiple times (and more).

For those who are curious, here’s the link to my Github project. Here’s the link to the visualizer if you’re interested.

A special thanks to Jamie Dawson, for getting me started on this project with his insightful article on the subject.