Check out my article on medium to understand how the algorith works
This project is a sorting algorithm project from the 42 School curriculum. The goal is to sort an array of integers using only very limited operations.
The program takes an array of integers as an argument and sorts it using the push swap algorithm. The algorithm is composed of two stacks, named a and b. a initially contains a random number of positive or negative integers without any duplicates, and b is empty. The goal is to sort the numbers in a in ascending order.
The program is limited to these commands 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 |
First clone this repository:
git clone [email protected]:lucafisc/push_swap.git
Enter the directory:
cd push_swap
To start the sorting program, frist compile the files with the command make. Then, run the program with the command ./push_swap int1 int2 int3 .... The program will output the sequence of commands needed to sort the array.
You can see an animation of how the algorithm works using the visualizer found in this repo: https://github.com/o-reo/push_swap_visualizer
 |
|---|
| The animation shows the Push Swap algorithm in action, sorting 100 numbers in ascending order. |
| Stack size | Average no. of commands |
|---|---|
| 5 | 7 |
| 100 | 605 |
| 500 | 5219 |
I got the highscore in the stats (means my algorithm used very few commands) and tested with this repo: https://github.com/louisabricot/push_swap_tester