This project involves sorting data on a stack, with a limited set of instructions, and the smallest number of moves. To make this happen, you have to manipulate various sorting algorithms and choose the most appropriate solution(s) for optimized data sorting.
- Status: finished
- Result: 125%
- Observations: (null)
Sort stack a
, with the help of stack b
, using the smallest number of moves and a limited set of operations.
- The game is composed of 2 stacks named
a
andb
. - To start with:
a
contains a random numbe of either positive or negative numbers without any duplications, passed via terminal arguments (you must handle wrong input).b
is empty.
- The goal is to sort in ascending order numbers into stack a.
- To do this you have the following operations at your disposal:
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
andsb
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
andrb
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
andrrb
at the same time.
- At the end stack
b
must be emtpy and all integers must be sorted in ascending order in stacka
.
My implementation of the operations in a doubly linked list:
I take different aproachs depending of the size of the stack.
-
1 numbers Allways sorted :D
-
2 numbers Easy,
sa
if second one if bigger than the first. -
3 numbers For 3 numbers it is easy, they are only 5 possible solutions, so a few if else was all I needed:
-
3 ~ 5 numbers This is when things get darker, to sort 4 or 5 arguments I just push 1 or 2 numbers from stack
a
tob
, making sure I left 3 arguments ona
, so now I can sort those 3 numbers with the sort 3 function. Once sorted I push back to stacka
the numbers on stackb
, making sure I push it in the correct positions, how? I just rotate the stack withra
andrra
, and push the number back when I can push it in the correct position. When done I just rotate the list until the smallest number is on top. -
5 ~ inf. After trying different algorithms and seeing them in action, I decided to use a chunk based one. Making a long history sort, I divide stack
a
into "chunks", for example:- 0 ~ 19: chunk 1
- 20 ~ 39: chunk 2
- 40 ~ 59: chunk 3
- 60 ~ 79: chunk 4
- 80 ~ 99: chunk 5
Now, I rotate stack a
searching for numbers in chunk 1, once I found one, I push it to b
. Once all the stack is pushed, I move to the next one, and so on until stack a
is empty.
To push the elements back to stack a
I just check for the bigger one, rotate with ra
or rra
, depending on wich one takes less moves, and push the element back, one by one, from bigger to smaller, and since they are sorted by chunks, I will not need to rotate too much to find the next one.
- Clone with "--recurse-submodules"
git clone --recurse-submodules https://github.com/izenynn/push_swap.git
- Compile using make
make
- Execute
push_swap
with the stacka
as parameter
./push_swap 4 3 1 0 2
- You can use other commands like
seq
andsort -R
to generate a random list, and make it complex
ARG=`seq -1000 1000 | sort -R | tail -n 500 | tr '\n' ' '`; ./push_swap $ARG
- If you can to use a checker, just use it as follows:
./push_swap 4 3 1 0 2 | ./push_swap_tester/checkers/checker_OS 4 3 1 0 2
- or
ARG="4 3 1 0 2"; ./push_swap $ARG | ./checker $ARG
- Checkers are cool but I would recommend you trying my tester,
push_swap_tester
, it is a gitsubmodule in this repo, more info about how to use it in thepush_swap_tester
push_swap_tester repo
To do this project we were given two checkers, one for Mac and another one for Linux, but what if we code our own checker?
This is the bonus part of the project, checker
is a program which will get as an argument the stack a formatted as a list of integers (just copy paste the push_swap
argument). It will parse the arguments and create the stack, just like push_swap
, and it will test your push_swap
works, let me explain.
The checker
program will take the output of push_swap
, and using ft_get_next_line
(get_next_line repo), it will copy the movements, and when finished, return OK
if the stack is sorted, or KO
if not.
Of course, checker
also handle errors, like no arguments, invalid arguments, wrong push_swap output (something different than a operation), etc.
- Compile
checker
with make
make checker
- Now just use it as the other checkers
./push_swap 3 2 1 0 4 | ./checker 3 2 1 0 4
- or
ARG="3 2 1 0 4"; ./push_swap $ARG | ./checker $ARG
Or of course you can test it with my tester push_swap_tester repo