This project has been created as part of the 42 curriculum by ymoumene.
push_swap is a program that outputs a sequence of instructions to sort a list of integers stored in a stack. The goal is to sort the stack using a limited set of operations, while minimizing the total number of commands.
The program uses two stacks:
- stack a, which initially contains the numbers to sort and have to be sorted.
- stack b, which is empty at the beginning and used as auxiliary storage
We also have a bonus that is a checker to verify that the instructions produced by push_swap correctly sort the stack a.
The main sorting strategy is based on the Longest Increasing Subsequence (LIS) algorithm. After the input values have been indexed, the program finds the longest subsequence that is already in increasing order and keeps those elements in stack A. The other elements are pushed to stack B. They are then inserted back into stack A by choosing the element with the lowest movement cost, combining rotations whenever possible. A final rotation places the smallest value at the top of stack A.
Keeping the LIS in stack A reduces the number of elements that need to be moved and therefore helps limit the total number of instructions produced by push_swap.
To run the program, first navigate to the project directory using a terminal.
in the terminal, use the bash command make, it will compile the main program, then use the command:
./push_swap
followed by the list you want to sort, the first argument is the top of the stack, here an example :
./push_swap 787 -15 0 435 526 627
the programm does not accept duplicates nor invalid characters, in this case he will display an error message :
./push_swap 56 -65 0 -56g
Error
if you want to check that the process does indeed sort the stack. A checker has been made for you :
make bonus
then use the command :
./checker
This will generate the executable checker.
You can then use it as follows:
./push_swap 3 2 1 | ./checker 3 2 1
The checker reads the instructions from standard input. it will display OK if the stack is sorted correctly or KO otherwise.
To get in hand with the project, you have to understand the concept of algorithm complexity:
https://en.wikipedia.org/wiki/Computational_complexity
You also have to learn the particularity of a stack :
https://en.wikipedia.org/wiki/Stack_(abstract_data_type)
I used AI during this project for:
-searching for algorithms to implement
-learning and understanding different algorithmic concepts
-learning a sorting algorithm (merge sort) and getting resources to implement it
-reviewing and rephrasing my README