The push_swap project is intended to sort a given list (numerical, non-repeating) using a limited set of instructions in the lowest number of "moves".
To complete this project, students have to implement a sorting algorithm of their choice. The algorithm's efficiency will be defined and evaluated as a measure of the number of actions it takes to sort the list. For my project, I implemented the algorithm detailed in Duarte Morais's GitHub (duarte3333).
I. Usage
II. Push_swap Rules
III. Program "Flow"
IV. Testing
./push_swap <Arguments>
eg:
./push_swap 35 28 8 16 61 6 60 56 72 22
• 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 : 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 : 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 : rra and rrb at the same time.
The first thing the program does is validate the input given — I call this step "parsing". During this step it checks if a proper amount of arguments were given and if these arguments followed the rules imposed by the subject. If the checks succeed, the arguments are stored in a linked list called stack_a, in the order they were given. Otherwise, the program prints "Error" and exits.
After parsing, the stack order is checked. If it is already sorted, the program frees the stack and exits. If the stack isn't sorted, the program proceeds to check which sort it runs — sort_2, sort_3, sort_4, sort_5, or the developed algorithm.
The algorithm implemented follows some very simple steps. To demonstrate these steps, we'll consider the following stack, and we'll apply the algorithm to it.
35 28 8 16 61 6 60 56 72 22 |
|
|---|---|
stack_a |
stack_b |
Firstly, we calculate the average of stack_a (x̄a) which in this case is x̄a = 36,4. Then we compare the value at the top of stack_a (na) with the calculated average. If na is greater than x̄a we use ra to place it at the bottom of the stack. Otherwise, we use pb to place na at the top of stack_b. After each move, we recalculate x̄a and compare it with the new number at the top of stack_a. We repeat this until there are only 5 values left on stack_a regardless of the amount of values we have initially — for example, if our list has 20 values, we repeat this until stack_a has 5 and stack_b has 15.
Applying this to our stack we get the following:
60 56 72 22 61 |
6 16 8 28 35 |
|---|---|
stack_a |
stack_b |
Now we sort the remaining 5 values of stack_a.
22 56 60 61 72 |
6 16 8 28 35 |
|---|---|
stack_a |
stack_b |
Next, we calculate the so called "best friend" of each value in stack_b — also known as the smallest number from stack_a which is bigger than the number from stack_b. So, for each value of our stack_b we get:
| 6 | 16 | 8 | 28 | 35 |
|---|---|---|---|---|
22 - 6 = 16 56 - 6 = 50 60 - 6 = 54 61 - 6 = 55 72 - 6 = 66 |
22 - 16 = 6 56 - 16 = 40 60 - 16 = 44 61 - 16 = 45 72 - 16 = 56 |
22 - 8 = 14 56 - 8 = 48 60 - 8 = 52 61 - 8 = 53 72 - 8 = 64 |
22 - 28 = -6 56 - 28 = 28 60 - 28 = 32 61 - 28 = 33 72 - 28 = 44 |
22 - 35 = -13 56 - 35 = 21 60 - 35 = 25 61 - 35 = 26 72 - 35 = 37 |
Using these pairs of values, the number of rotations (ra/rb or rra/rrb) needed to place each pair on top of their respective stacks is calculated (we call this number the cost).
| Number (stack_b) | "Best friend" (stack_a) | Cost Moves for B I Moves for A |
|---|---|---|
6 16 8 28 35 |
22 22 22 56 56 |
0 I 0 1 I 0 2 I 0 2 I 1 1 I 1 |
This pair is then placed at the top of each stack (if they were not already at the top), and we use pa to place nb at the top of stack_a. The previous steps (calculating the "best friend" for each value and the cost) are repeated until stack_b is empty.
35 56 60 61 72 6 8 16 22 28 |
|
|---|---|
stack_a |
stack_b |
Now all that is left to do is rotate stack_a (ra or rra) until it is sorted.
6 8 16 22 28 35 56 60 61 72 |
|
|---|---|
stack_a |
stack_b |
After the stack is sorted and the algorithm has stopped running, both stacks are freed from memory and the program exits.
In order to verify my program's efficiency, I used Yfu's push_swap tester to run several random lists of numbers in bulk. I recommend testing your push_swap yourself, then using this tester. Don't forget to test at least for assortments of 5, 10, 100, and 500 numbers.