As part of the 42 School curriculum i wrote this highly efficient sorting algorithm project in C coding language.
The goal is to sort a stack of integers using a limited set of operations and the minimum number of moves.
Visualizing the "dancing stacks" is the best way to understand how the algorithm works.
Here the video of the sorting: Push_swap Sorting Video
The push_swap program calculates and displays the smallest sequence of instructions to sort a list of integers. It uses two stacks, Stack A and Stack B, and a specific set of operations:
sa,sb,ss: Swap the first two elements of a stack.pa,pb: Push an element from one stack to another.ra,rb,rr: Rotate the stack (first element becomes last).rra,rrb,rrr: Reverse rotate (last element becomes first).
In the implementation I used a Greedy Cost-Based Algorithm (often referred to as "Turk Algorithm"):
- It handles small cases (n <= 5) with optimized hardcoded logic.
- For larger sets, it pushes elements to Stack B, leaving only 3 in Stack A.
- It then calculates the "cost" for each element in B to be moved back to A in the correct position.
- It executes the move with the lowest combined cost (rotations in A + rotations in B).
- Finally, it performs a final adjustment to ensure the smallest number is at the top.
Open a terminal in the project directory and run:
makeThis will generate the push_swap executable.
Run the program by passing a list of integers:
./push_swap 4 67 3 87 23It will output the sequence of commands.
It is possible to use the provided checker_Mac or checker_linux to verify if the output correctly sorts the numbers:
ARG="4 67 3 87 23"; ./push_swap $ARG | ./checker_Mac $ARGIf it displays OK, the sort was successful.
The Makefile includes scripts to stress-test the algorithm and ensure it meets the 42 School efficiency requirements.
These commands will run the program multiple times with different random sets and report the worst-case scenario (the maximum number of moves it took).
- For 100 numbers: (Target: < 700 moves for maximum score in the evaluation)
make 100
- For 500 numbers: (Target: < 5500 moves for maximum score in the evaluation)
make 500
These commands run the program through the checker_Mac or checker_linux 10 times with random inputs to verify that the sorting is always correct.
- Check 100 numbers:
make 100check - Check 500 numbers:
make 500check
Here I am listing one of the many web-based visualizers that helps to visualise the algorithm in action, by simply copying the output of the program and the initial numbers. (Following a sample of 300 numbers and operations ready to be pasted)