Push_Swap - Learning Sorting Algorithms

Summary

This project challenge is to sort data on a stack using a limited set of instructions in the minimum possible number of operations. To succeed, one needs to manipulate different sorting algorithms and choose the most appropriate solution(s) for optimized data sorting.

Push_Swap is a simple yet effective algorithmic exercise: sorting data. It takes a set of integers, two stacks, and a set of instructions to manipulate these stacks. The goal is to create a C program, named "push_swap", which calculates and displays the smallest program, made of Push_Swap instructions, that sorts the integers passed as parameters.

Skills Gained

• Developed a strong understanding of different sorting algorithms (Quicksort, Insertion sort, Bubble sort) and their complexities.
• Gained a deeper understanding of the stack data structure and how to manipulate it.
• Enhanced problem-solving skills by choosing the most appropriate sorting algorithm based on requirements.
• Improved coding skills in C.
• Learned to measure and optimize the performance of algorithms.
• Gained experience in writing clean, efficient, and well-documented code.

Mandatory Part

Rules

• Your project must be written in C.
• The game consists of 2 stacks named a and b.
• At the start:
  • Stack a contains an arbitrary amount of positive and/or negative numbers without duplicates.
  • Stack b is empty.
• The goal of the game is to sort the numbers in stack a in ascending order.

For this, you have the following operations:

• 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 on a. Do nothing if b is empty.
• pb (push b): Take the first element at the top of a and put it on 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 "push_swap" Program

The aim of the "push_swap" program is to sort the stacks using the smallest possible number of operations. It must be written in C and conform to the following requirements:

• Your Makefile must compile your source files without relinking.
• Global variables are forbidden.
• The program must take stack a as a list of integers as an argument. The first argument is at the top of the stack.
• The program must display a program composed of the shortest possible sequence of operations that sorts stack a, with the smallest number at the top.
• Instructions must be separated by a '\n' and nothing else.
• The goal is to sort the integers with the fewest possible operations. During the evaluation, the number of instructions calculated by your program will be compared to a maximum allowed number of operations. If your program outputs a sequence that is too long, or if the list of integers is not sorted, you will score 0.
• If no arguments are specified, the program must display nothing and return the prompt.
• In the event of an error, you must display "Error" followed by a '\n' on the error output. For example, if some parameters are not numbers, do not fit into an int, or if there are duplicates.

Maximum allowed number of operations

Find below the maximum number of operations allowed for different numbers of integers in the stack:

Number of Integers	Maximum Number of Operations
3	3
5	12
100	700
500	5500

Usage

./push_swap 4 67 3 87 23

./push_swap 0 9 1 3 2 6 5 4 8 7

You can also use the provided tester which will check if the output of your program is a valid sequence of instructions to sort the stack.

chmod +x test.sh
./test.sh

Bonus Part

The bonus part of the project involves creating your own checker program. This will allow you to verify that the list of instructions generated by the "push_swap" program correctly sorts the stack passed as a parameter.

The "checker" Program

The "checker" program must also be written in C. It should take the same argument as the push_swap execurable. It must then wait and read instructions from the standard input, each instruction followed by a '\n'. Once all instructions have been read, the program applies them to its stack of integers, effectively following the main executable's orders.

If, following execution, stack A is sorted and stack B is empty, the program must display "OK" followed by a '\n' on the standard output. Otherwise, it must display "KO" followed by a '\n' on the standard output.

In the event of an error, the program must display "Error" followed by a '\n' on the error output.

If the program receives no arguments, it must display nothing and return the prompt.

Additionally, if the program receives an argument different from the list of integers, it has no way of knowing if the argument list is the same as the one used by the push_swap program. In this case, the program's bethavior is undefined.

Usage

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

ARG="0 9 1 3 2 6 5 4 8 7"; ./push_swap $ARG | ./checker $ARG

You can also use the provided tester which will check if the output of your program is a valid sequence of instructions to sort the stack.

chmod +x test.sh
make
./test.sh bonus

Troubleshooting

If you encounter the following error when running make:

make: *** No rule to make target 'libft.a', needed by 'push_swap'.  Stop.

You can fix it by running the following command:

git submodule update --init --recursive