Skip to main content

​
Strategy Overview

Push Swap uses different sorting strategies based on the size of the input:
  • 2 elements: Single swap operation
  • 3 elements: Specialized sort_three() algorithm
  • 4+ elements: Advanced sort_big_stacks() algorithm using cost analysis

​
Strategy Selection

The main sorting function determines which strategy to use (push_swap.c:59-70): 
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);
}

​
Sorting Three Elements

For exactly 3 elements, Push Swap uses a specialized algorithm that handles all possible permutations efficiently.

​
Algorithm

Location: push_swap.c:15-42 
void sort_three(t_list **a)
{
    int val1;
    int val2;
    int 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);
}

​
Case Analysis

The algorithm handles all 6 possible permutations of 3 elements:
Condition: val1 > val2 && val2 > val3Operations: sa → rraSteps:
  1. Swap first two: [2, 3, 1]
  2. Reverse rotate: [1, 2, 3]
Cost: 2 operations
Condition: val1 > val2 && val2 < val3 && val1 > val3Operations: raSteps:
  1. Rotate: [1, 2, 3]
Cost: 1 operation
Condition: val1 > val3 && val2 < val3 (simplified)Operations: raNote: This case overlaps with Case 2 logicCost: 1 operation
Condition: val1 < val2 && val2 > val3 && val1 > val3Operations: rraSteps:
  1. Reverse rotate: [1, 2, 3]
Cost: 1 operation
Condition: val1 < val2 && val2 > val3 && val1 < val3Operations: sa → raSteps:
  1. Swap first two: [3, 1, 2]
  2. Rotate: [1, 2, 3]
Cost: 2 operations
Condition: val1 > val2 && val2 < val3 && val1 < val3Operations: saSteps:
  1. Swap first two: [1, 2, 3]
Cost: 1 operation

​
Optimality

The sort_three() algorithm is optimal - it never uses more than 2 operations for any 3-element permutation, which is the theoretical minimum for some cases.

​
Sorting Large Stacks

For 4 or more elements, Push Swap uses the Turk Algorithm - a sophisticated approach based on cost analysis.

​
Algorithm Overview

Location: sort_big_stacks.c:53-75 
void sort_big_stacks(t_list **a, t_list **b)
{
    int len_a;

    len_a = stack_len(*a);
    // Push first 2 elements to B without analysis
    if (len_a-- > 3 && !is_stack_sorted(*a))
        pb(b, a, false);
    if (len_a-- > 3 && !is_stack_sorted(*a))
        pb(b, a, false);
    // Push remaining elements (except last 3) using cost analysis
    while (len_a-- > 3 && !is_stack_sorted(*a))
    {
        init_nodes_a(*a, *b);
        move_a_to_b(a, b);
    }
    // Sort final 3 elements in A
    sort_three(a);
    // Move all elements back from B to A
    while (*b)
    {
        init_nodes_b(*a, *b);
        move_b_to_a(a, b);
    }
    // Ensure minimum value is at top
    current_index(*a);
    min_on_top(a);
}

​
Phase 1: Move A to B

The algorithm first moves all elements except 3 from Stack A to Stack B, using cost analysis to determine the optimal order.

​
Initial Pushes

if (len_a-- > 3 && !is_stack_sorted(*a))
    pb(b, a, false);
if (len_a-- > 3 && !is_stack_sorted(*a))
    pb(b, a, false);
  • The first 2 elements are pushed to B without cost analysis
  • This provides initial elements in B for target node calculation
  • Optimization: Skip if stack becomes sorted

​
Cost-Based Movement

Location: sort_big_stacks.c:37-51 
static void move_a_to_b(t_list **a, t_list **b)
{
    t_list *cheapest_node;

    cheapest_node = get_cheapest(*a);
    if (cheapest_node->above_median
        && cheapest_node->target_node->above_median)
        rotate_both(a, b, cheapest_node);
    else if (!(cheapest_node->above_median)
        && !(cheapest_node->target_node->above_median))
        rev_rotate_both(a, b, cheapest_node);
    prep_for_push(a, cheapest_node, 'a');
    prep_for_push(b, cheapest_node->target_node, 'b');
    pb(b, a, false);
}
Steps:
  1. Find the cheapest node to move (lowest push_cost)
  2. Optimize by rotating both stacks simultaneously if possible
  3. Position the node at the top of Stack A
  4. Position its target at the top of Stack B
  5. Push to Stack B

​
Phase 2: Sort Remaining Three

Once only 3 elements remain in Stack A: 
sort_three(a);
Uses the specialized 3-element algorithm described above.

​
Phase 3: Move B to A

Move all elements from Stack B back to Stack A in sorted order. Location: sort_big_stacks.c:15-19 
static void move_b_to_a(t_list **a, t_list **b)
{
    prep_for_push(a, (*b)->target_node, 'a');
    pa(a, b, false);
}
Process:
  1. init_nodes_b() calculates target positions in A
  2. Position target node at top of A
  3. Push from B to A
Note: No cost analysis needed here - elements are moved in order from top of B.

​
Phase 4: Final Rotation

current_index(*a);
min_on_top(a);
Ensures the minimum value is at the top of Stack A, completing the sort. Location: min_on_top.c:15-24 
void min_on_top(t_list **a)
{
    while ((*a)->nbr != find_min(*a)->nbr)
    {
        if (find_min(*a)->above_median)
            ra(a, false);
        else
            rra(a, false);
    }
}

​
Rotation Optimizations

​
Rotate Both (rr)

Location: sort_big_stacks.c:21-27 
static void rotate_both(t_list **a, t_list **b, t_list *cheapest_node)
{
    while (*b != cheapest_node->target_node && *a != cheapest_node)
        rr(a, b, false);
    current_index(*a);
    current_index(*b);
}
Purpose: When both the node and its target are above median, rotate both stacks simultaneously. Benefit: Saves operations by combining two separate rotations into one.

​
Reverse Rotate Both (rrr)

Location: sort_big_stacks.c:29-35 
static void rev_rotate_both(t_list **a, t_list **b, t_list *cheapest_node)
{
    while (*b != cheapest_node->target_node && *a != cheapest_node)
        rrr(a, b, false);
    current_index(*a);
    current_index(*b);
}
Purpose: When both the node and its target are below median, reverse rotate both stacks simultaneously. Benefit: Reduces total operation count compared to separate reverse rotations.

​
Prep for Push

Location: stack_utils.c:43-62 
void prep_for_push(t_list **stack, t_list *top_node, char stack_name)
{
    while (*stack != top_node)
    {
        if (stack_name == 'a')
        {
            if (top_node->above_median)
                ra(stack, false);
            else
                rra(stack, false);
        }
        else if (stack_name == 'b')
        {
            if (top_node->above_median)
                rb(stack, false);
            else
                rrb(stack, false);
        }
    }
}
Purpose: Positions a specific node at the top of its stack. Logic:
  • If node is above median: Use forward rotation (ra/rb)
  • If node is below median: Use reverse rotation (rra/rrb)
Why: Choosing the shorter rotation path minimizes operations.

​
Performance Characteristics

Input SizeStrategyTypical OperationsWorst Case
2 elementsSingle swap11
3 elementssort_three()1-22
5 elementssort_big_stacks()~7-12~12
100 elementssort_big_stacks()~500-700~700
500 elementssort_big_stacks()~5000-5500~5500
The algorithm’s efficiency comes from always choosing the cheapest move and optimizing rotations when both stacks can rotate in the same direction.

Build docs developers (and LLMs) love

Get started for freeTalk to us