Skip to main content

​
Overview

The Turkish (Turk) algorithm is a greedy, cost-based approach used by Push Swap to sort stacks with more than 3 elements. It works by calculating the “cost” of moving each element and always choosing the cheapest move. The algorithm is implemented in sort_big_stacks.c:53 and uses helper functions from init_a_to_b.c and init_b_to_a.c.

​
Algorithm Phases

The Turkish algorithm operates in three distinct phases:
1

Phase 1: Push to B

Push all elements except 3 from Stack A to Stack B, using cost analysis to minimize operations.
2

Phase 2: Sort remaining 3

Use the optimized sort_three() function to sort the remaining 3 elements in Stack A.
3

Phase 3: Push back to A

Push all elements back from Stack B to Stack A in the correct sorted positions.

​
Implementation Details

​
Main Function

The core logic is in sort_big_stacks(): 
void sort_big_stacks(t_list **a, t_list **b)
{
    int len_a;

    len_a = stack_len(*a);
    // Push first two elements without cost 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 using cost analysis
    while (len_a-- > 3 && !is_stack_sorted(*a))
    {
        init_nodes_a(*a, *b);
        move_a_to_b(a, b);
    }
    
    // Sort the final 3 elements
    sort_three(a);
    
    // Push everything back to A
    while (*b)
    {
        init_nodes_b(*a, *b);
        move_b_to_a(a, b);
    }
    
    current_index(*a);
    min_on_top(a);
}
The first two elements are pushed immediately without cost analysis to establish a reference in Stack B for subsequent cost calculations.

​
Cost Analysis System

The heart of the Turkish algorithm is its cost calculation mechanism, implemented in init_a_to_b.c.

​
Node Initialization

Before each move, init_nodes_a() prepares all nodes with necessary metadata: 
void init_nodes_a(t_list *a, t_list *b)
{
    current_index(a);      // Set index and above_median for each node
    current_index(b);
    set_target_a(a, b);    // Find target position in B for each node in A
    cost_analysis_a(a, b); // Calculate push cost
    set_cheapest(a);       // Mark the cheapest node
}

​
Index and Median Tracking

The current_index() function assigns an index to each node and determines if it’s above or below the median: 
void current_index(t_list *stack)
{
    int i;
    int median;

    i = 0;
    if (!stack)
        return;
    median = stack_len(stack) / 2;
    while (stack)
    {
        stack->index = i;
        if (i <= median)
            stack->above_median = true;
        else
            stack->above_median = false;
        stack = stack->next;
        i++;
    }
}
The above_median flag is critical for optimization - it determines whether to use rotate (ra/rb) or reverse rotate (rra/rrb) to bring an element to the top.

​
Target Node Selection

For each element in Stack A, the algorithm finds its target position in Stack B: 
static void set_target_a(t_list *a, t_list *b)
{
    t_list *current_b;
    t_list *target_node;
    long best_match_index;

    while (a)
    {
        best_match_index = LONG_MIN;
        current_b = b;
        while (current_b)
        {
            // Find the largest number in B that's still smaller than a->nbr
            if (current_b->nbr < a->nbr && current_b->nbr > best_match_index)
            {
                best_match_index = current_b->nbr;
                target_node = current_b;
            }
            current_b = current_b->next;
        }
        // If no smaller number exists, target is the maximum
        if (best_match_index == LONG_MIN)
            a->target_node = find_max(b);
        else
            a->target_node = target_node;
        a = a->next;
    }
}
The target selection strategy:
  • Find the largest number in B that is still smaller than the current number in A
  • If no such number exists, the target is the maximum element in B

​
Cost Calculation

The cost_analysis_a() function calculates how many operations it would take to push each element from A to B: 
static void cost_analysis_a(t_list *a, t_list *b)
{
    int len_a;
    int len_b;

    len_a = stack_len(a);
    len_b = stack_len(b);
    while (a)
    {
        // Cost to bring element to top of A
        a->push_cost = a->index;
        if (!(a->above_median))
            a->push_cost = len_a - (a->index);
        
        // Add cost to bring target to top of B
        if (a->target_node->above_median)
            a->push_cost += a->target_node->index;
        else
            a->push_cost += len_b - (a->target_node->index);
        
        a = a->next;
    }
}
Cost components:
  1. Rotation cost in A: Number of rotations to bring element to top
    • If above median: use ra (cost = index)
    • If below median: use rra (cost = len - index)
  2. Rotation cost in B: Number of rotations to bring target to top
    • Same logic as Stack A
This cost calculation doesn’t account for simultaneous rotations (rr/rrr), which are optimized later in move_a_to_b().

​
Finding the Cheapest Node

The set_cheapest() function marks the node with the lowest cost: 
void set_cheapest(t_list *stack)
{
    long cheapest_value;
    t_list *cheapest_node;

    if (!stack)
        return;
    cheapest_value = LONG_MAX;
    while (stack)
    {
        if (stack->push_cost < cheapest_value)
        {
            cheapest_value = stack->push_cost;
            cheapest_node = stack;
        }
        stack = stack->next;
    }
    cheapest_node->cheapest = true;
}

​
Move Optimization

When moving the cheapest node from A to B, the algorithm optimizes by rotating both stacks simultaneously when possible: 
static void move_a_to_b(t_list **a, t_list **b)
{
    t_list *cheapest_node;

    cheapest_node = get_cheapest(*a);
    
    // Both above median: rotate both together
    if (cheapest_node->above_median
        && cheapest_node->target_node->above_median)
        rotate_both(a, b, cheapest_node);
    
    // Both below median: reverse rotate both together
    else if (!(cheapest_node->above_median)
        && !(cheapest_node->target_node->above_median))
        rev_rotate_both(a, b, cheapest_node);
    
    // Finish positioning both nodes at the top
    prep_for_push(a, cheapest_node, 'a');
    prep_for_push(b, cheapest_node->target_node, 'b');
    
    // Push from A to B
    pb(b, a, false);
}

​
Simultaneous Rotation

When both the cheapest node and its target are on the same side of the median, the algorithm uses combined operations:
  • rr: Rotate both stacks up (when both above median)
  • rrr: Rotate both stacks down (when both below median)
This reduces the total operation count significantly.

​
Pushing Back from B to A

Once Stack A has only 3 elements (which are sorted), the algorithm pushes everything back from B to A: 
void init_nodes_b(t_list *a, t_list *b)
{
    current_index(a);
    current_index(b);
    set_target_b(a, b);
}
The target selection for B to A is reversed:
  • Find the smallest number in A that is still larger than the current number in B
  • If no such number exists, the target is the minimum element in A
static void set_target_b(t_list *a, t_list *b)
{
    while (b)
    {
        best_match_index = LONG_MAX;
        current_a = a;
        while (current_a)
        {
            if (current_a->nbr > b->nbr && current_a->nbr < best_match_index)
            {
                best_match_index = current_a->nbr;
                target_node = current_a;
            }
            current_a = current_a->next;
        }
        if (best_match_index == LONG_MAX)
            b->target_node = find_min(a);
        else
            b->target_node = target_node;
        b = b->next;
    }
}

​
Key Advantages

Greedy Efficiency

Always picks the cheapest move, ensuring locally optimal decisions

Median Optimization

Uses above_median flag to minimize rotation operations

Simultaneous Operations

Exploits rr/rrr to reduce total operation count

Adaptive Strategy

Recalculates costs after each move, adapting to the current state

​
Example Walk-through

Let’s see how the algorithm handles a stack: [5, 2, 8, 1]
1

Initial State

Stack A: [5, 2, 8, 1]
Stack B: []
2

Push first two

Operations: pb pb
Stack A: [8, 1]
Stack B: [2, 5]
3

Analyze costs

  • Element 8: target=5, cost=1 (already at top)
  • Element 1: target=2, cost=2 (rra + rb)
Cheapest: 8 (cost=1)
4

Move 8 to B

Operations: pb
Stack A: [1]
Stack B: [5, 2, 8]
5

Push back

Operations: pa pa pa
Stack A: [1, 2, 5, 8]
Stack B: []
This is a simplified example. The actual algorithm would handle this differently as it requires at least 3 elements in A before starting to push back.

​
Summary

The Turkish algorithm is a sophisticated greedy approach that:
  1. Calculates the cost of every possible move
  2. Always executes the cheapest move
  3. Optimizes by using simultaneous operations
  4. Adapts dynamically as the stacks change
This makes it highly efficient for sorting large stacks while maintaining a reasonable operation count.

Build docs developers (and LLMs) love

Get started for freeTalk to us