42 Algorithm Project - Sort problem
Given a set of integers, sort it using a predefined set of instructions using two stacks. The instruction set is defined below. This program outputs a program in push_swap instructions that sorts the input integers.
For the following instructions, if the instruction is not possible, the part of it that can't be executed won't.
Code | Instruction | Action |
---|---|---|
sa |
swap a | swaps the 2 top elements of stack a |
sb |
swap b | swaps the 2 top elements of stack b |
ss |
swap a + swap b | both sa and sb |
pa |
push a | moves the top element of stack b at the top of stack a |
pb |
push b | moves the top element of stack a at the top of stack b |
ra |
rotate a | shifts all elements of stack a from bottom to top |
rb |
rotate b | shifts all elements of stack b from bottom to top |
rr |
rotate a + rotate b | both ra and rb |
rra |
reverse rotate a | shifts all elements of stack a from top to bottom |
rrb |
reverse rotate b | shifts all elements of stack b from top to bottom |
rrr |
reverse rotate a + reverse rotate b | both rra and rrb |
Run make
.
./push_swap 1 2 3 4
- For 100 numbers:
ARG=`ruby -e "puts (0..100).to_a.shuffle.join(' ')"`; ./push_swap $ARG | wc -l
1 point | 2 points | 3 points | 4 points | 5 points |
---|---|---|---|---|
1500 | 1300 | 1100 | 900 | 700 |
✅ | ✅ | ✅ | ✅ | ✅ |
- For 500 numbers:
ARG=`ruby -e "puts (0..100).to_a.shuffle.join(' ')"`; ./push_swap $ARG | wc -l
1 point | 2 points | 3 points | 4 points | 5 points |
---|---|---|---|---|
11500 | 10000 | 8500 | 7000 | 5500 |
✅ | ✅ | ✅ | ✅ | ✅ |
To use a visualizer like the top gif, refer directly here : https://github.com/o-reo/push_swap_visualizer