Push_swap: Sorting Without Traditional Algorithms

Finally, this is it, I got it working! I’ve struggled on this project far more than I wanted to, like way too long…

This was my first deep dive into algorithmic challenge since I began my studies at **Hive Helsinki**. Having heard about push_swap and it’s complexity, I was ready for the challenge. I set a goal for myself to create my very own algorithm . It took me a month of writing different versions and a huge amount of paper (yes this project demands a lot of visualisation on paper).

Explore my GitHub repository if you want to see my mess😉

General You will be provided with stack A, filled with numbers in a random sequence. Your task is to sort these numbers using specified instructions, assisted by another stack, B.

**Random order**                             **After execution**
5                                            1
1                                            2
3                                            3
2                                            4
4                                            5
- -                                          - -
a b                                          a b

Without further ado, let me explain you my approach to the project. I’ll walk you through my thought process throughout the project so hopefully you don’t have to make the same mistakes I did.

Introduction

This project will make you sort data on a stack, with a limited set of instructions, using the lowest possible number of actions. To succeed you’ll have to manipulate various types of algorithms and choose the most appropriate solution (out of many) for an optimized data sorting.

You have at your disposal a set of integer values, 2 stacks, and a set of instructions to manipulate both stacks.

Your goal? Write a program in C called push_swap which calculates and displays on the standard output the smallest program, made of Push swap language instructions, that sorts the integers received as arguments.

Easy? We’ll see…

The Rules

You have 2 stacks named a and b.

At the beginning: The stack a contains a random amount of negative and/or positive numbers which cannot be duplicated. The stack b is empty.

The goal is to sort in ascending order numbers into stack a. To do so you have the following operations at your disposal:

**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 :** Perform sa and sb at the same time.  
**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.  
**rr :** Perform ra and rb at the same time.  
**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.  
**rrr :** Perform rra and rrb at the same time.

Example:

**Init a and b:**
2
1
3
6
5
8 
- -
a b

**Exec sa:**
1
2
3
6
5
8
- -
a b

**Exec pb pb pb:**
6 3
5 2
8 1
- -
a b

**Exec rra rrb (equalent to rrr):**
6 3
5 2
8 1
- -
a b

**Exec sa:**
5 3
6 2
8 1
- -
a b

**Exec pa pa pa:**
1
2
3
5
6
8
- -
a b

Data structure

It’s worth mentioning what data structure I am using and why I chose it. After examining the task I decided to choose a single linked list for my data structure, not because it would be the most efficient but rather a great opportunity for me to learn linked lists on a deeper level. In my opinion you can use an array of characters as well, it shouldn’t make a difference.

My node looks like this:

typedef struct s_stack
{
 int    value;
 int    cost;
 struct s_stack *next;
} t_stack;

1. Version

First I wanted to understand the task so I wrote a basic algorithm where I moved every element to B stack. Then I rotated the B stack to get the largest number on top, then pushed it to back the A stack. For rotation of the B stack I only used RB so total moves with 500 random numbers was around 50 000. I knew it was way too much but at least I understood the task and was ready to tackle a more efficient algorithm.

2. Version

In my second version I improved the algorithm by using rb or rrb.

We locate the largest number in the stack and calculate the distance to the top. If the number is closer to the end of the stack we reverse rotate it, if closer to the top then normal rotate (we use this optimization in every version).

As you can see, it’s more efficient to reverse rotate the stack B

After we bring the largest element on top in stack B we push it to stack A. We repeat these steps as long as stack B isn’t empty.

Here is a brief visualization of the algorithm and how does it work:

Big shout out to Yooh from 42 Seoul for making this push_swap visualizer.

[embed]

3. Version

I quickly realised that my previous version wouldn’t cut it. I had to get the number of instructions fewer then 7 000 with 500 numbers. That meant that I needed to change my whole approach. I watched and watched my algorithm sort different numbers and I realised that I only one stack makes the whole work in sorting the stack and just pushes the largest number back. I needed to utilize both stacks to work simultaneously. Then I came up with a whole new idea. I wouldn’t think of the numbers as stacks, but rather as wheels. This would allow me to push any number from A to B if the number would be in the correct place, so not only the largest number.

Here is a visualisation:

First step is to move the 2 top numbers from stack A to stack B, to make it a “wheel” as well. After that we calculate the cost for every number in stack A. Cost is calculated with this formula:

cost = moves_to_top + destination_moves;

Basically we calculate the cost to rotate the number to the top of A stack and cost to rotate the B stack to get the correct placement to top.

We can see that we were able to push the number 5 from stack A to stack B without any rotations, because the number 5 would be in a correct position in stack B. The correct position is checked with this formula:

If A_num is greater than the top number in stack B &&
A_num smaller than the last number in stack B.

Edge cases if A_num is greater || A_num is smaller than all numbers in stack B.
In both of these cases we rotate the largest element in stack B to top
and and push the number on top of the largest.
If the A_num was the largest, then we leave it on the top of stack.
If A_num was the smallest number, then we do RRB and get the new smallest
number on the bottom of stack B

That is the core principle of the algorithm. We calculate the cost of all numbers in stack A to get them in the correct position in B stack. After that we always move the cheapest number from A to B and calculate the costs again for all numbers.

This difference drastically decreased the number of instructions with 500 numbers.

Here is the visualisation:

[embed]

4. Version

This was milestone for me, I was so happy getting those numbers down. I had one more thing to do. I needed to figure out a way to use double rotations (rr & rrr). The way I did this is the following:

a_direction = 0;
b_direction = 0;

If we use ra to get the cheapest element to top of A
a_direction = 1 // ra
else
a_direction = 2 // rra

Then we check the same with stack B
if we need ra to get the correct place in B stack on top
b_direction = 1 // rb
else
b_direction = 2 // rrb

So we have 2 flags for the cheapest number and they represent the way in which we will rotate the stacks. So every time we rotate the stacks we check if a_direction == b_direction. If the variables are the same, it means that we will rotate them in the same direction. Then we execute rr or rrr till one of the stacks has reached the correct position, and continue to rotate the other stack with normal rotations if the correct position hasn’t been reached yet.

Here is a visualisation on how this change affects the algorithm:

[embed]

Conclusion

That’s a wrap on my push_swap jorney.

Through the countless lines of code, the numerous debug sessions late night and the never-ending cycle of errors this is it. It was tough, but really enlightening experience. And it thought me that coding isn’t just about getting the syntax right or memorizing specific algorithms. I’ts about tackling a problem, breaking it down and not giving up even if it feels that it’s far beyond your skill set.

For those who stuck with me through this post, thank you. I hope seeing my journey from chaotic code mess to structured, efficient solution helps you in some way.

Feel free to hit me up on LinkedIn. if you’re curious about my approach or want me to explain it.

See you in my next post :)