Computers are all about information. To store it, to send it, but most importantly to categorize it so humans can make sense of it. This is why sorting algorithms are at the core of almost any application. I am proud to have finally written one!

The subject

The objective of the project is simple. The program must take a list of numbers and sort it from smallest to biggest. However, you are limited to a list of certain instructions, which creates the real exercise. You can read more in the subject below:

How my program works

Given the limitations by the type of operations, I discovered that the radix algorithm in binary base would be best fit to create an algorithm, that is well-balanced between efficiency and simplicity. I added a few simple optimizations in my implementations to boost the efficiency to the level required by the subject. This is how it works step by step:

1. The input is checked on formatting and the numbers are stored as a linked list
2. The list gets simplified, by replacing the absolute value of each number with their index (zero-based) in the sorted list.
   1. After all, sorting a list like "14232, -234, 8, 24" could be done with the exact same steps as for "3, 0, 1, 2". Using radix, the latter would take many less steps than the former.
   2. It also helps to deal with the fact for how negative numbers are represented in the memory, which our sorting algorithm wouldn't be able to handle otherwise.
3. For as many bits it takes to represent the biggest index of the list, we iterate the following actions over the least significant bit to the most significant for each number of the list:
   1. If the bit is positive, we push it to 'stack b'
   2. If the bit is negative, we leave it in 'stack a'
   3. We push all numbers in 'stack b' back to 'stack a' in reverse order after every iteration

What I learned

It gave great satisfaction to see this algorithm in action and really experience first-hand what it means that computers are masters of repetition and how well code scales. Thanks to this great visualization tool, I could literally see and feel my baby algorithm grow up to the point where it flawlessly sorts a list of numbers of any size, as if it were nothing. It was almost surreal that something that I created did a hugely better job at something than myself. The perfect reminder for why I chose to learn about the inner workings of computers and how they are so powerful and how much there is still to discover the impact they will have on human life.

Thanks for reading and check the code out for yourself here:

Yannick / push_swap · GitLab

GitLab.com

GitLab