351 words
2 minutes
Push_swap — Stack Sorting & Cost-Optimized Move Reduction
Push_swap — Constrained Stack Sorting
Push_swap is a 1337 / 42 curriculum algorithm project. The goal is to sort a disordered list of integers on a primary stack (Stack A) using an auxiliary stack (Stack B) and a restricted instruction set, minimizing the total number of operations executed.
Instruction Set
| Operation | Action |
|---|---|
sa / sb / ss | Swap first 2 elements of stack A / stack B / both |
pa / pb | Push top element from B to A / from A to B |
ra / rb / rr | Rotate stack up (first element becomes last) |
rra / rrb / rrr | Reverse rotate stack down (last element becomes first) |
Algorithmic Architecture
1. Small Sets (N <= 5)
- 3 Elements: Evaluated with a simple decision tree requiring at most 2 operations.
- 5 Elements: Smallest values are located, rotated to the top with minimal directional cost, pushed to Stack B, and reinserted after sorting the remaining 3 elements in Stack A.
2. Large Sets (N = 100 and N = 500): Mechanical Greedy Cost Evaluation
For larger datasets, a greedy cost-based algorithm (often referred to as the Turk algorithm) was implemented:
- Pre-pushing: Two elements are pushed to Stack B to seed the target stack.
- Cost Calculation: For every node remaining in Stack A, the algorithm calculates:
- Rotations required to bring the node to the top of Stack A (
ravsrra). - Rotations required to position Stack B so that the incoming element lands in its sorted position (
rbvsrrb). - Shared dual rotations (
rrorrrr) where both stacks rotate simultaneously in the same direction.
- Rotations required to bring the node to the top of Stack A (
- Execution: The node with the absolute lowest combined mechanical cost is chosen and moved.
- Reintegration: Once Stack A contains only 3 elements, it is sorted, and elements in Stack B are pushed back into their exact insertion slots in Stack A.
- Final Realignment: Stack A is rotated until the minimum element rests at index 0.
typedef struct s_stack{ int value; int index; int push_cost; bool above_median; bool cheapest; struct s_stack *target_node; struct s_stack *next; struct s_stack *prev;} t_stack;Performance Results
- 100 Numbers: Average of ~580 moves (Well within the 700-operation threshold for 100/100).
- 500 Numbers: Average of ~4,900 moves (Well within the 5,500-operation threshold).
- Complexity: average time, zero heap memory leaks verified under Valgrind.
Sphynx | Ismail Larhrib