Page Background Animation
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#

OperationAction
sa / sb / ssSwap first 2 elements of stack A / stack B / both
pa / pbPush top element from B to A / from A to B
ra / rb / rrRotate stack up (first element becomes last)
rra / rrb / rrrReverse 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:

  1. Pre-pushing: Two elements are pushed to Stack B to seed the target stack.
  2. Cost Calculation: For every node remaining in Stack A, the algorithm calculates:
    • Rotations required to bring the node to the top of Stack A (ra vs rra).
    • Rotations required to position Stack B so that the incoming element lands in its sorted position (rb vs rrb).
    • Shared dual rotations (rr or rrr) where both stacks rotate simultaneously in the same direction.
  3. Execution: The node with the absolute lowest combined mechanical cost is chosen and moved.
  4. 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.
  5. 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: O(Nlog⁡N)O(N \log N) average time, zero heap memory leaks verified under Valgrind.