Skip to main content

​
Introduction

Push Swap solves the sorting problem using two stacks (A and B) and a limited set of operations. The algorithm adapts its strategy based on the size of the input, using different approaches for small and large stacks to minimize the number of operations.

​
Two-Stack Mechanism

The algorithm operates with two stacks:
  • Stack A: Contains the initial unsorted numbers and will hold the final sorted result
  • Stack B: Used as auxiliary storage during the sorting process

​
Available Operations

The algorithm can only use these stack operations:
  • sa, sb, ss: Swap the first two elements
  • pa, pb: Push from one stack to another
  • ra, rb, rr: Rotate (shift up)
  • rra, rrb, rrr: Reverse rotate (shift down)

​
Sorting Strategies by Size

The algorithm selects different strategies based on stack size, as implemented in push_swap.c:59: 
void sort_stack(t_list **a, t_list **b)
{
    int size;

    size = ft_stack_size(*a);
    if (size == 2)
        sa(a, false);
    else if (size == 3)
        sort_three(a);
    else
        sort_big_stacks(a, b);
}

​
Size 2: Direct Swap

For two elements, the algorithm simply uses sa to swap if needed. This is the optimal solution requiring at most 1 operation.

​
Size 3: Hardcoded Solution

For three elements, sort_three() uses a hardcoded decision tree that handles all 6 possible permutations. Each case is solved with the minimal number of operations (0-2 operations).
push_swap.c
void sort_three(t_list **a)
{
    int val1, val2, val3;

    val1 = (*a)->nbr;
    val2 = (*a)->next->nbr;
    val3 = (*a)->next->next->nbr;
    
    if (val1 > val2 && val2 > val3)
    {
        sa(a, false);
        rra(a, false);
    }
    else if (val1 > val2 && val2 < val3 && val1 > val3)
        ra(a, false);
    else if (val1 > val3 && val2 < val3)
        ra(a, false);
    else if (val1 < val2 && val2 > val3 && val1 > val3)
        rra(a, false);
    else if (val1 < val2 && val2 > val3 && val1 < val3)
    {
        sa(a, false);
        ra(a, false);
    }
    else if (val1 > val2 && val2 < val3 && val1 < val3)
        sa(a, false);
}

​
Size 4+: Turkish Algorithm

For larger stacks, the algorithm uses the Turkish (Turk) algorithm, which is a greedy cost-based approach. This is implemented in sort_big_stacks() and is detailed in the Turkish Algorithm page.

​
High-Level Flow

1

Check if sorted

Before starting, the algorithm checks if the stack is already sorted using is_stack_sorted(). If sorted, no operations are performed.
2

Select strategy

Based on the stack size, the appropriate sorting function is called:
  • 2 elements → sa
  • 3 elements → sort_three()
  • 4+ elements → sort_big_stacks()
3

Execute sorting

The selected strategy performs the sorting operations, outputting each operation to stdout.
4

Return sorted stack

Stack A contains the sorted numbers in ascending order, and Stack B is empty.

​
Optimization Philosophy

The algorithm prioritizes:
  1. Operation count: Minimizing the total number of operations
  2. Efficiency: Using combined operations (rr, rrr, ss) when both stacks need the same action
  3. Greedy approach: Always selecting the cheapest move for large stacks
  4. Median awareness: Choosing rotate vs reverse rotate based on element position
The algorithm always leaves Stack A sorted in ascending order with the smallest element at the top.

​
Next Steps

Turkish Algorithm

Deep dive into the cost-based sorting strategy for large stacks

Complexity Analysis

Understand time and space complexity of the algorithm

Build docs developers (and LLMs) love

Get started for freeTalk to us