Because swap_push isn’t as natural
The program push_swap will sort random integers on a stack, with a limited set of instructions, trying to use the least stack operations to get an ascending sorted stack.
- Clone it like this:
git clone
- Compile the program:
make all
- Execute the program:
./push_swap [Numbers to sort separated by space]
You can put in any amount of numbers. The programm will then print the actions needed to sort the numbers. - Check if right actions were used
./push_swap [Numbers to sort separated by space] | ./checker [Numbers to sort separated by space]
If it displays OK everything worked fine!
The game is composed of 2 stacks named A and B.
Starting Point:
- Stack_A contains random numbers of either positive or negative numbers without any duplicates.
- Stack_B is empty
The goal is to sort in ascending order numbers into stack.
The operations the program can do, are limited to the following set:
Operations | Description |
---|---|
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 algorithm starts by first using the LIS-Algorithm LIS-Algorithm on the aStack, if the Stack has <50 numbers.
After the LIS-Check the non-LIS numbers will be pushed to bStack, pre-sorted in 3-4 chunks.
The last Algorithm is an Insertion-Sort. The algorithm loops through the numbers of bStack and looks for the least needed operations to push a number from bStack to the right place on the aStack.
For more information look into the subject pdf
*All 42 projects must be written in C (later C++) in accordance to the 42 School Norm.
- All variables have to be declared and aligned at the top of each function
- Each function can not have more then 25 lines
- Projects should be created with allowed std functions otherwise it is cheating