push_swap is a sorting algorithm project from the 42 curriculum.
It consists in writing a program that sorts a stack of integers using a limited set of operations and the smallest number of moves possible.
The goal of push_swap is to sort a list of integers with the lowest number of operations, using only two stacks (A and B) and a predefined set of instructions (like sa, pb, rra, etc.).
You will:
- Implement a sorting algorithm optimized for minimal operations
- Use data structures such as linked lists
- Optimize performance for different input sizes (up to 500 numbers)
- Write a checker to validate the correctness of instructions
| Instruction | Description |
|---|---|
sa |
swap the first two elements of A |
sb |
swap the first two elements of B |
ss |
sa and sb at the same time |
pa |
push the top of B onto A |
pb |
push the top of A onto B |
ra |
rotate A (first becomes last) |
rb |
rotate B |
rr |
ra and rb at the same time |
rra |
reverse rotate A |
rrb |
reverse rotate B |
rrr |
rra and rrb at the same time |