push_swap

This is an algorithm project where the goal is to sort a given list of random numbers using a limited set of operations, aiming to minimize the number of actions.

Final score

125%

The grade is based on the efficiency of the program's sorting process:

• Sorting 3 values: No more than 3 actions.
• Sorting 5 values: No more than 12 actions.
• Sorting 100 values: Points are awarded based on the number of actions:
  • 5 points for fewer than 700 actions
  • 4 points for fewer than 900 actions
  • 3 points for fewer than 1100 actions
  • 2 points for fewer than 1300 actions
  • 1 point for fewer than 1500 actions
• Sorting 500 values: Points are awarded based on the number of actions:
  • 5 points for fewer than 5500 actions
  • 4 points for fewer than 7000 actions
  • 3 points for fewer than 8500 actions
  • 2 points for fewer than 10000 actions
  • 1 point for fewer than 11500 actions

Usage

To get started with this project, simply clone the repository and compile the program:

make
make bonus

This will produce 2 programs named push_swap and checker.

The push_swap program accepts a list of integers as arguments and generates a sequence of instructions to sort the stack. For example:

./push_swap 30 10 40 20

This will produce a series of instructions that will sort the stack [30, 10, 40, 20].

The checker program accepts a list of integers as arguments and reads a series of instructions from standard input. It applies these instructions to the stack and verifies whether the stack is sorted. For example:

./checker 30 10 40 20
sa
pb
ra
pb
rra
pa
pa

This will execute the instructions on the stack [30, 10, 40, 20] and output OK if the stack is sorted, or KO if it is not.

Here are the available operations:

• sa: Swap the top two elements in stack A.
• sb: Swap the top two elements in stack B.
• ss: Execute both sa and sb at the same time.
• pa: Move the top element from stack B to the top of stack A.
• pb: Move the top element from stack A to the top of stack B.
• ra: Rotate stack A (move the first element to the end).
• rb: Rotate stack B (move the first element to the end).
• rr: Execute both ra and rb at the same time.
• rra: Reverse rotate stack A (move the last element to the top).
• rrb: Reverse rotate stack B (move the last element to the top).
• rrr: Execute both rra and rrb at the same time.

Quick sort algorithm

The goal is to sort the stack using the fewest instructions possible. To do this, you need to devise a strategy that makes the most of the limited set of operations:

1. Pre-sort the numbers for indexing: Arrange the numbers in ascending order to assign them positions or indices.
2. Divide into 3 parts: The largest group stays in stack A, the smallest group is placed at the bottom of stack B, and the middle group goes on top of stack B.
3. Use quicksort on all three parts: Recursively move the smaller half to stack B, and then the larger half to stack A.
4. Optimize the instructions: For instance, if RA and RB are executed consecutively, replace them with a single RR to minimize operations.

---