A highly optimized sorting algorithm using two stacks with limited operations
Achieving exceptional performance with median-based partitioning and greedy optimization
Stack Size | Maximum Moves | Minimum Moves | Average Moves | Grade |
---|---|---|---|---|
100 elements | 667 | 535 | 597 | โญโญโญโญโญ |
500 elements | 5,110 | 4,459 | 4,797 | โญโญโญโญโญ |
Well below the limits: 700 moves (100 elements) and 5,500 moves (500 elements)
This Push Swap implementation features a sophisticated hybrid sorting algorithm that combines:
- Median-Based Partitioning: Intelligent division of data using statistical median
- Greedy Return Algorithm: Cost-optimized element placement from stack B to A
- Dual Stack Optimization: Simultaneous operations on both stacks when beneficial
- Adaptive Sorting: Dynamic strategy selection based on input size
- Smart Median Selection: Dynamically calculates optimal pivot points
- Cost Matrix Analysis: Evaluates all possible moves to find minimum cost operations
- Dual Rotation Optimization: Performs
rr
andrrr
when both stacks benefit - Target Index Prediction: Efficiently determines optimal placement positions
push_swap/
โโโ ๐ sort/ # Core sorting algorithms
โ โโโ complex_sort.c # Advanced median + greedy algorithm
โ โโโ simple_sort.c # Optimized for โค5 elements
โ โโโ begin_sort.c # Entry point and strategy selector
โ โโโ initialize_sort.c # Stack initialization and preprocessing
โโโ ๐ operations/ # Stack operation implementations
โ โโโ push_operations.c # pa, pb
โ โโโ rotate_operations.c # ra, rb, rr
โ โโโ reverse_rotate_operations.c # rra, rrb, rrr
โ โโโ swap_operations.c # sa, sb, ss
โโโ ๐ utils/ # Utility functions and validation
โ โโโ check_input.c # Input validation and error handling
โ โโโ tools1.c # Core utility functions
โ โโโ tools2.c # Target finding and cost calculation
โ โโโ tools3.c # Additional helper functions
โโโ ๐ bonus/ # Checker program
โ โโโ checker.c # Main checker implementation
โ โโโ checker_utils.c # Checker utility functions
โโโ ๐ printf/ # Custom printf implementation
โโโ ๐ include/ # Header files
โโโ push_swap.h # Main project header
โโโ bonus.h # Bonus checker header
- Simultaneous rotation of both stacks when beneficial
- Reduces total move count by up to 20%
- Intelligent detection of dual operation opportunities
- Real-time calculation of move costs for each element
- Considers both rotation directions (forward/reverse)
- Optimizes for minimum total operations
- Binary search-inspired position detection
- Handles circular stack nature elegantly
- O(log n) complexity for target identification
- Different algorithms for different input sizes
- Specialized micro-optimizations for small arrays
- Dynamic threshold adjustment
- GCC compiler with C99 support
- Make utility
- Unix-like environment (Linux/macOS) or WSL on Windows
# Clone the repository
git clone <your-repo-url>
cd push_swap
# Compile the project
make
# Compile with bonus (checker)
make bonus
# Clean object files
make clean
# Full clean (remove executable)
make fclean
# Basic usage
./push_swap 3 2 1 4 5
# Test with random numbers
./push_swap $(shuf -i 1-100 -n 100 | tr '\n' ' ')
# Using with checker (bonus)
./push_swap 3 2 1 | ./checker 3 2 1
# Performance testing
./push_swap $(shuf -i 1-500 -n 500 | tr '\n' ' ') | wc -l
Operation | Description | Implementation |
---|---|---|
sa |
Swap first two elements of stack A | swap_a() |
sb |
Swap first two elements of stack B | swap_b() |
ss |
Execute sa and sb simultaneously |
swap_swap() |
pa |
Push top element from B to A | push_a() |
pb |
Push top element from A to B | push_b() |
ra |
Rotate stack A (first โ last) | rotate_a() |
rb |
Rotate stack B (first โ last) | rotate_b() |
rr |
Execute ra and rb simultaneously |
rotate_rotate() |
rra |
Reverse rotate stack A (last โ first) | reverse_rotate_a() |
rrb |
Reverse rotate stack B (last โ first) | reverse_rotate_b() |
rrr |
Execute rra and rrb simultaneously |
reverse_rotate_rotate() |
For comprehensive testing and performance validation, you can use this excellent tester:
๐ Push-Swap-Tester by gemartin99
# Clone and setup the tester
git clone https://github.com/gemartin99/Push-Swap-Tester.git
cd Push-Swap-Tester
bash push_swap_test.sh [path_to_your_push_swap]
This tester provides:
- โ Automated testing for different stack sizes
- ๐ Performance metrics and statistics
- ๐ฏ Visual feedback on results
- ๐ Grade calculation based on move counts
#!/bin/bash
# Test with different sizes
for size in 10 50 100 500; do
echo "Testing size: $size"
for i in {1..10}; do
./push_swap $(shuf -i 1-$size -n $size | tr '\n' ' ') | wc -l
done | sort -n
done
- โ All input validation (duplicates, non-integers, edge cases)
- โ Memory leak testing with Valgrind
- โ Stress testing with various input sizes
- โ Edge case handling (empty, single element, pre-sorted)
Aspect | Complexity | Details |
---|---|---|
Time Complexity | O(n log n) | Median finding + greedy optimization |
Space Complexity | O(n) | Two stacks + auxiliary arrays |
Move Complexity | O(nยฒ) worst | O(n log n) average with optimizations |
- ๐ฅ Perfect Score: 125/100 (with bonus)
- ๐ฏ Exceptional Performance: Well below move limits
- ๐ง Algorithm Innovation: Custom median + greedy hybrid approach
- ๐ก๏ธ Robust Error Handling: Comprehensive input validation
- ๐ Scalable Design: Efficient for all input sizes
The algorithm uses a sophisticated median selection that:
- Calculates true statistical median for optimal partitioning
- Adapts partition size based on remaining elements
- Minimizes worst-case scenarios through intelligent pivoting
int total_cost = rotation_cost_a + rotation_cost_b + alignment_cost;
Where each cost considers:
- Forward vs reverse rotation efficiency
- Current stack positions
- Future move implications
The algorithm intelligently detects when both stacks can be rotated in the same direction:
if (can_rotate_both_forward(a_target, b_target))
use_rr_operations();
else if (can_rotate_both_reverse(a_target, b_target))
use_rrr_operations();
Algorithm Type | 100 Elements | 500 Elements | Efficiency |
---|---|---|---|
This Implementation | ~597 moves | ~4,797 moves | โญโญโญโญโญ |
Basic Bubble Sort | ~4,950 moves | ~124,750 moves | โญ |
Quick Sort Variant | ~800 moves | ~6,200 moves | โญโญโญ |
Other Median Approaches | ~650 moves | ~5,100 moves | โญโญโญโญ |
Results may vary based on input distribution
Feel free to:
- Report bugs or suggest improvements
- Submit performance optimizations
- Add additional test cases
- Enhance documentation
- 42 School Curriculum: Advanced algorithmic thinking
- Median of Medians Algorithm: Optimal pivot selection
- Greedy Algorithms: Cost optimization strategies
- Stack-Based Sorting: Constraint-based algorithm design
This project is part of the 42 School curriculum. Feel free to study and learn from the implementation while respecting academic integrity policies.
Made with โค๏ธ and lots of โ at 42 Beirut
Turning constraints into creativity, one algorithm at a time
This project includes a comprehensive checker program that validates the correctness of push_swap solutions!
The checker is a separate program that:
- โ Reads the same input as push_swap (stack of integers)
- ๐ Accepts operation instructions from stdin (sa, sb, pa, pb, ra, rb, etc.)
- ๐ฏ Validates the solution by executing each operation
- โ
Outputs result:
OK
if sorted correctly,KO
if not,Error
if invalid
# Compile the checker
make bonus
# Test a manual solution
echo -e "pb\nra\npa" | ./checker 3 2 1
# Validate push_swap output
./push_swap 3 2 1 4 | ./checker 3 2 1 4
# Test with complex input
./push_swap $(shuf -i 1-100 -n 100 | tr '\n' ' ') | ./checker $(shuf -i 1-100 -n 100 | tr '\n' ' ')
- ๐ง Robust Input Parsing: Handles all input formats (multiple args or single string)
- ๐ก๏ธ Error Detection: Validates operations and catches invalid instructions
- ๐ Memory Management: Efficient allocation and cleanup
- ๐ฏ Precise Validation: Ensures final stack A is sorted and stack B is empty
- Custom Line Reader: Reads operations from stdin without using
get_next_line
- Operation Parser: Validates and executes each push_swap operation
- Stack State Tracking: Maintains accurate stack states throughout execution
- Comprehensive Error Handling: Detects duplicates, invalid operations, and memory issues
All 11 push_swap operations are fully supported:
sa
,sb
,ss
(swap operations)pa
,pb
(push operations)ra
,rb
,rr
(rotate operations)rra
,rrb
,rrr
(reverse rotate operations)
# Quick validation test
./push_swap 5 4 3 2 1 | ./checker 5 4 3 2 1
# Expected output: OK
# Test with invalid operations
echo -e "invalid_op\npa" | ./checker 3 2 1
# Expected output: Error
# Test edge cases
./push_swap | ./checker
# Expected output: OK (empty input)
The checker program demonstrates additional mastery of:
- ๐ stdin/stdout handling
- ๐ง String parsing and validation
- ๐ฏ Algorithm verification
- ๐ก๏ธ Edge case management