Push_Swap Tutorial

Push_swap is an algorithm project at school 42. I’ll introduce this project briefly and share an algorithm to solve it : radix sort.

Advantages of this algorithm : easy to implement, stable

Disadvantages of this algorithm : passable but won’t get full score (unless you can find a way to optimize it)

Introduction

First, we start with two stacks called A and B.

A is filled with some random integers (without duplicate) and B is empty. We can perform certain instructions on these stacks, and the goal is to sort all these integers with the least instructions possible.

If the original stacks look like this

9

4

8

7

----------     ----------

a              b

Our goal is to print a list of instructions that can make the stacks sorted like this

4

7

8

9

----------     ----------

a              b

And here is the list of instructions that we can perform :

sa (swap a) : Swap the top two numbers in A

sb (swap b) : Swap the top two numbers in B

ss : sa + sb

ra (rotate a) : Top number in A goes to bottom of A

rb (rotate b) : Top number in B goes to bottom of B

rr : ra + rb

rra (reverse rotate a) : Bottom number in A goes to top of A

rra (reverse rotate b) : Bottom number in B goes to top of B

rrr : rra + rrb

pa (push a) : Top number in B goes to top of A

pb (push b) : Top number in A goes to top of B

This is how it should look like when we run our program

Step by step, we can see these instructions really sort the numbers

If our instruction list is correct, we’ll be rated by the amount of instructions we use.

With 3 numbers, we need to sort it with not more than 3 instructions.

With 5 numbers, we need to sort it with not more than 12 instructions.

With 100 numbers, we can get

5 points if the size of the list of instructions is less than 700

4 points if the size of the list of instructions is less than 900

3 points if the size of the list of instructions is less than 1100

2 points if the size of the list of instructions is less than 1300

1 points if the size of the list of instructions is less than 1500

With 500 numbers, we can get

5 points if the size of the list of instructions is less than 5500

4 points if the size of the list of instructions is less than 7000

3 points if the size of the list of instructions is less than 8500

2 points if the size of the list of instructions is less than 10000

1 points if the size of the list of instructions is less than 11500

According to unreliable sources, we need to get at least 6 points to pass.

Algorithm

Step 1 : Parsing, put numbers in the stack A if no errors are detected

Step 2 : Check if the numbers in A are all sorted. If so, end the program without printing anything. It’d be preferable to write a function A_is_sorted()

Step 3 : If the size of A ≤ 5, call function sort_small_stack(). Else, call function sort_big_stack()

In this article, we’ll focus on the implementation of function sort_big_stack()

We can start with this sorting algorithm : Radix sort

Radix Sort

You can watch this short video, but I’ll explain it anyway.

Radix sort is an efficient algorithm to sort non-negative integers with time complexity O(n * d) where d = floor(log_b(k) + 1) for base = b (Thanks to the correction by Dmitry)

For example, we can sort following list of integers with this algorithm

87 487 781 100 101 0 1

Imagine there are 10 boxes labeled 0, 1, 2, …, 9

Start from the least significant digit (which is the digit in 1’s place), we put each number into the box which its digit corresponds to.

In the example, 87 has 7 in 1’s place, hence we put it in box 7. 487 also has 7 in 1’s place, so it should be placed in box 7 too (right behind 87) … And we repeat this process until every number is in one of the boxes.

box 0    100    0
box 1    781    101    1    
box 2    
box 3
box 4
box 5
box 6
box 7     87    487
box 8
box 9

After that, we connect every number according to the order of boxes

100 0 781 101 1 87 487

As we can see, the numbers are sorted according to the digit in 1’s place. For those with the same digit in 1’s place, they’re sorted according to their order in the original list.

We repeat this process for the digit in 10’s place.

100 has 0 in 10’s place so we put it in box 0, 0 has 0 in 10’s place so we put it in box 0 right after 100 …

box 0    100    0    101    1
box 1    
box 2    
box 3
box 4
box 5
box 6
box 7    
box 8    781   87    487
box 9

And connect it

100 0 101 1 781 87 487

At this moment, the numbers are sorted according to the digit in 10’s place, then the digit in 1’s place.

Same things for the digit in 100’s place. (This is will be the last time since the largest number in the list is 781, which has only 3 digits.)

box 0      0      1       87
box 1    100    101
box 2    
box 3
box 4    487
box 5
box 6
box 7    781
box 8    
box 9

And connect

0 1 87 100 101 487 781

Now, the numbers are all sorted.

Fast and elegant as this algorithm is, we need some adaptation to be able to use this on our push_swap. First, we must simplify the numbers.

Simplify numbers

As we mentioned before, this algorithm is for non-negative integers. However, we’ll have negative numbers in this project, so we should simplify the numbers before we start.

For example, if we need to sort these numbers

87 -487 781 -100 101 0 1

Our goal is to perform some operations to make them

-487 -100 0 1 87 101 781

If we replace them with 0, 1, 2, … like

-487 -100 0 1 87 101 781
   0    1 2 3  4   5   6

The original list

87 -487 781 -100 101 0 1

just becomes

4 0 6 1 5 2 3

The operations to make 87 -487 781 -100 101 0 1 sorted can also make 4 0 6 1 5 2 3 sorted and vice versa.

So, instead of sorting 87 -487 781 -100 101 0 1, now we only need to sort 4 0 6 1 5 2 3.

With this idea, we can simplify any list of integers to make them in the range [0,N) ( ≥ 0 and < N, N is the size of the list). Here is a short implementation in C++.

(If you are not familiar with the syntax of C++, just think vector<int> as integer array, and sort as a function that sorts an array in ascending order.)

vector<int> input;

//parse the numbers into input ...
//reminder : there is no duplicate

vector<int> copy = input; // copy the numbers from input

sort(copy.begin(), copy.end());

for(int i = 0 ; i < input.size() ; ++i) 
    for(int j = 0 ; j < copy.size() ; ++j)
        if (input[i] == copy[j]) {
            input[i] = j;
            break ;
        }

//put input into stack a ...

/*
Remark : This is actually not the most efficient way to implement them. If you want a more efficient program, please learn about binary search or unordered_map (hash)
*/

Now, every number in the array input is in the range [0,N), thus we can use radix sort to sort them.

However, using 10 boxes is not a good idea for push_swap because we have only 2 boxes. Obviously, 2 boxes will be more suitable in this case, which means we should put numbers in base 2.

To manipulate numbers in base 2, we can either save the numbers as strings composed of 0 and 1, or use bitwise operations like some cool programmers.

Bitwise operations

Same, you can read this article but I’ll explain it anyway.

C Bitwise Operators: AND, OR, XOR, Complement and Shift Operations

Today we’ll use two bitwise operatiors in C/C++, they’re

>> (Right shift)

and

& (Bitwise AND)

The >> operator shifts all bits toward right. Let’s see how it works with an example.

Suppose we have a number

int num = 36;

In base 2 it’s

0000 ... 0010 0100（32 bits in total）

If we use the >> operator in C

printf("%d\n", num>>2); // output is 9

Output will be 9. Why ?

0000 ... 0010 0100 -> 36

Right shift 2 bits

0000 ... 0000 1001 -> 9

It’s because 36 in base 10 is 100100 in base 2, after right shift 2 bits it becomes 1001, which is 9 in base 10.

Some exercises that you can try. Think first, then verify your answers with C.

8>>1 == ?

5>>2 == ?

2>>4 == ?

87>>3 == ? (Hint : 87 in base 10 is 1010111)

Then, the Bitwise AND operator (&).

For every bit, & works as below

1 & 1 == 1
1 & 0 == 0
0 & 1 == 0
0 & 0 == 0

For two integers, & will perform on every bit. For example

printf("%d\n", 6&5); //output is 4

will print 4. Because

6   : 0000 ... 0 1 1 0
5   : 0000 ... 0 1 0 1

6&5 : 0000 ... 0 1 0 0 -> 4

For the bit in 1’s place, 6 and 5 has 0 and 1 respectively. 0&1 == 0 so this bit for 6&5 is 0.

For the bit in 10’s place, 6 and 5 has 1 and 0 respectively. 1&0 == 0 so this bit for 6&5 is 0.

For the bit in 100’s place, 6 and 5 has 1 and 1 respectively. 1&1 == 1 so this bit for 6&5 is 1.

All the other bits are 0 for both 6 and 5, hence 6&5 == 000000 … 0100 in base 2, which is 4 in base 10.

Some more examples

2   : 0000 ... 0 0 1 0
5   : 0000 ... 0 1 0 1

2&5 : 0000 ... 0 0 0 0 -> 0

--------------------------------------------------------------------

15  : 0000 ... 1 1 1 1
9   : 0000 ... 1 0 0 1

2&5 : 0000 ... 1 0 0 1-> 9

Some exercises that you can try. Think first, then verify your answers with C.

5&10 == ?

12&23 == ?

Now, we are finally ready to implement push_swap with radix sort

Radix sort on push_swap

Back to the example quite above, if we want a list of instructions to sort

87 -487 781 -100 101 0 1

The result is the same as sorting

4 0 6 1 5 2 3

In base 2, it’ll be

100 000 110 001 101 010 011

In stacks, it looks like

100

000

110

001

101

010

011

----------     ----------

a              b

As in radix sort, we need two boxes for 0 and 1 respectively. Here we treat A as box 1 and B as box 0. Then, we start from the rightmost bit to the leftmost bit.

At the i-th digit from the right, if the i-th digit of the top number of A is 0, we perform pb to put this number in stack B. Else, we perform ra to leave it in stack A. After we perform one operation on each number, each of them is in the box that corresponds to its digit, as how we put numbers in the boxes in radix sort.

After we do this for the first bit (the rightmost bit), it must look like this.

               010

001            110

101            000

011            100

----------     ----------

a              b

After that, we perform pa until there are no numbers in stack B, as we connect the numbers in radix sort.

100

000

110

010

001

101

011

----------     ----------

a              b

We repeat this process for the second and the third bit.

-----The-Second-Bit------

               101

110            001

010            000

011            100

----------     ----------

a              b

---------Connect---------

100

000

001

101

110

010

011

----------     ----------

a              b

------The-Third-Bit------

               011

100            010

101            001

110            000

----------     ----------

a              b

---------Connect---------

000

001

010

011

100

101

110

----------     ----------

a              b

After we repeat three times, the numbers are sorted because the biggest number in the list (6 in base 10, 110 in base 2) has only 3 bits.

So this is how we sort them.

To achieve it with C++, it'd be like

int size = a.size();

int max_num = size - 1; // the biggest number in a is stack_size - 1

int max_bits = 0; // how many bits for max_num 

while ((max_num >> max_bits) != 0) ++max_bits;

for (int i = 0 ; i < max_bits ; ++i) // repeat for max_bits times
{
    for(int j = 0 ; j < size ; ++j)
    {

        int num = a.top(); // top number of A

        if ((num >> i)&1 == 1) ra(); 
        // if the (i + 1)-th bit is 1, leave in stack a

        else pb();
        // otherwise push to stack b

    }

    // put into boxes done

    while (!b.empty()) pa(); // while stack b is not empty, do pa
    
    // connect numbers done

}

The trickiest part must be the condition if ((num>>i)&1 == 1). The result of (num>>i)&1 must be 0 or 1, which is the value of the (i + 1)-th bit of num.

For example, (5>>2)&1 == 1 because

 5       : 101
 5>>2    :   1
(5>>2)&1 :   1

(8>>2)&1 == 0 because

 8       : 1000
 8>>2    :   10
(8>>2)&1 :    0

That's how we can implement the sort_big_stack() function. If you finish it and test it (the tester is below), you will see when stack_size is 100, there are about 1084 instructions, when stack_size is 500, there are about 6756 instructions, which are good enough to pass.

Question : Why the instruction amounts remain invariable even with different input ? (It’s not the problems of tester, go check the test_case if you don’t believe it.)

Apart from that, we can also implement it in other ways like

bool is_sorted(stack<int> & a);
// please implement this function by yourself :)

int size = a.size();

for (int i = 0 ; !is_sorted(a) ; ++i)
{

    for(int j = 0 ; j < size ; ++j)
    {

        int num = a.top();

        if ((num >> i)&1) ra();

        else pb();

    }

    while (!b.empty()) pa();
}

You can try to analyze pros and cons for these different ways of implementation.

Also, Some common mistakes :

for (int j = 0 ; j < a.size() ; ++j) // ... (x)

for (int j = 0 ; j < size ; ++j)     // ... (o)

Think carefully, what's the difference between these two loops ?

Anyway, that's how we complete push_swap with radix sort. If you meet any difficulties, the tools below can probably help you. Or you can comment to ask questions or give some advice. Good luck :)

Tools

For subject and some useful tools (radix sort visualizer)

LeoFu9487/push_swap_tutorial

Tester

LeoFu9487/push_swap_tester