A sorting algorithm project from 42 School
Push_swap is an individual project at 42 School that challenges students to sort a stack of integers using two stacks and a limited set of operations. The objective is to achieve a fully sorted stack in the fewest moves possible, emphasizing algorithm optimization and efficient stack manipulation.
For this project, I implemented the Turkish algorithm, a proven strategy for solving Push_swap efficiently, inspired by this resource from its creator. To meet the bonus requirements—which demand sorting within an even stricter move limit—I optimized the algorithm by checking if both numbers to be moved are above or below the median. This allowed me to perform simultaneous rotations (e.g., rr or rrr) when possible, reducing the total number of moves.
- Sorting Algorithm: Utilizes the Turkish algorithm for optimal stack sorting.
- Operations: Implements all required stack operations:
sa,sb,ss— Swap the top two elements of stack A, B, or both.pa,pb— Push an element from stack A to B or vice versa.ra,rb,rr— Rotate stack A, B, or both upward.rra,rrb,rrr— Reverse rotate stack A, B, or both downward.
- Optimization: Enhanced the Turkish algorithm to perform simultaneous rotations when both numbers are on the same side of the median, minimizing move count.
- Bonus Achievement: Meets the bonus criteria by staying below the required move threshold.
Clone the repository and use the following commands in your terminal:
# Compile the project
make all
# Remove object files
make clean
# Remove object files and executable
make fclean
# Clean and recompile
make re
To run the program, provide a list of integers as arguments:
./push_swap 3 1 4 2
The implementation was thoroughly tested using the following tools:
- Push_swap Visualizer : A tool that allows step-by-step visualization of the sorting process.
- Push_swap Tester : A combined visualizer and tester to verify both correctness and efficiency of moves.
Additionally, custom test cases were created to check edge cases and ensure compliance with bonus requirements.
Here’s my score for the Push_swap project:
- Turkish Algorithm Explanation : A comprehensive guide written by the algorithm’s creator, which was the basis for this implementation.
Feel free to reach out or contribute to this project on GitHub!