Push swap (42 School)

Push swap is a project about stack sorting algorithms. Using only 2 stacks and a initial set of numbers it must sort all numbers in ascendant order in the smallest number of instructions possible.

About The Project

Push swap takes any set of numbers as arguments and prints every instruction needed to sort all numbers. There are 2 stacks, stack A and stack B. Initially all numbers are pushed into stack A, stack B remains empty. Push swap needs to find the smallest set of instructions to sort the numbers with the help of stack B. The limited set of instructions that can be used to sort the stack are these:

• 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.

How to use

The program can be executed like this ./push_swap 5 0 -1 2 3 or ./push_swap "5 0 -1 2 3"

In order to test if push swap is correctly sorting the numbers another executable was created, the checker. This second program needs to be executed after push swap through a pipe and passing the same arguments as the first. It will read the set of instructions sent by push swap and check if that set correctly sorts the numbers, it should be executed like this:

ARG="4 67 3 87 23"; ./push_swap $ARG | ./checker $ARG

If push swap printed a correct set of instructions the checker prints 'OK', if the set doesn't sort the numbers it will print 'KO'. In case there is an error in the arguments, like duplicated numbers, it prints 'Error'.

Getting Started

In order to run the program first clone the repository:

git clone git@github.com:ferri17/push_swap.git

Open the folder:

cd push_swap/

Compile the program:

make

Run the program:

./push_swap "3 1 2"

To compile the checker program use:

make bonus