This project is about sorting data on a stack with a limited set of instructions, using the lowest possible number of actions. It aims to teach students about how to manipulate various types of algorithms and choose the most appropriate solution (out of many) for an optimized data sorting.
There are two stacks a
and b
. At the beginning, stack a
contains the numbers to be sorted and stack b
is empty. Only eleven stack operations are allowed. All of them are listed below:
Abbreviation | Stack operation | Description |
---|---|---|
sa |
swap a | Swap the first 2 elements at the top of stack a . |
sb |
swap b | Swap the first 2 elements at the top of stack b . |
ss |
swap both | 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 . |
pb |
push b | Take the first element at the top of a and put it at the top of b . |
ra |
rotate a | Shift up all elements of stack a by 1. |
rb |
rotate b | Shift up all elements of stack b by 1. |
rr |
rotate both | ra and rb at the same time. |
rra |
reverse rotate a | Shift down all elements of stack a by 1. |
rrb |
reverse rotate b | Shift down all elements of stack b by 1. |
rrr |
reverse rotate both | rra and rrb at the same time. |
The algorithm implemented was radix sort with bitwise operations to make it possible to work with only two stacks. The table below lists the project's efficiency to sort 100 and 500 random numbers respectively from grade 5 (best performance) to grade 1 (worst performance).
Grade | Stack operations to sort 100 numbers | Stack operations to sort 500 numbers | Project performance for sorting 100 numbers | Project performance for sorting 500 numbers |
---|---|---|---|---|
5 | less than 700 | less than 5500 | - | - |
4 | less than 900 | less than 7000 | - | 6756 |
3 | less than 1100 | less than 8500 | 1025 | - |
2 | less than 1300 | less than 10000 | - | - |
1 | less than 1500 | less than 11500 | - | - |
git clone [email protected]:ygor-sena/42cursus-push-swap.git
make
ARG=$(shuf -i 0-2000 -n 500)
This command generates 500 random numbers between 0 and 2000.
./push_swap $ARG
If you want to run the program looking for memory leaks, just start it as follows:
valgrind --leak-check=full --show-leak-kinds=all ./push_swap $ARG
After a valid argument is received, the program will start to sort the given numbers and print to the standard output all stack operations executed in order to accomplish its task. To count the number of operations, just run the program as follows:
./push_swap $ARG | wc -l
In this example, to sort 500 random numbers with radix sort, the output of the total stack operations done will be roughly 6756.
-
General reference books:
- BHARGAVA, Aditya. Grokking algorithms: an illustrated guide for programmers and other curious people. 2016.
- CORMEN et all. Introduction to Algorithms. 4th edition. 2022.
- FEOFILOFF, Paulo. Algoritmos em C. 2009.
-
Algorithm efficiency and visualization:
- Paula Hemsi's push_swap operations visualizer by phemsi-a.
- About sorting algorithms efficiency by Leonardo Galler and Matteo Kimura.
-
Tutorials by other 42's students: