Skip to main content

​
What is Push Swap?

Push Swap is an algorithmic sorting challenge that sorts a collection of integers using two stacks and a constrained set of operations. The goal is to sort the numbers in ascending order on stack A using the minimum number of moves possible.
Push Swap is a classic algorithmic problem from the 42 school curriculum that teaches optimization, data structures, and algorithm design.

​
The Problem

You are given:
  • Stack A: Contains a random set of integers
  • Stack B: Empty stack used as auxiliary storage
  • A set of operations: Limited moves to manipulate both stacks
The challenge is to sort all numbers in stack A in ascending order (smallest on top) using the fewest operations.

​
The Turkish Algorithm

This implementation uses the Turkish Algorithm (also known as the Turk Algorithm), an efficient approach for sorting with two stacks. The algorithm works by:
  1. Analyzing costs: Each element is assigned a “push cost” representing the number of operations needed to move it to its correct position
  2. Finding targets: For each element in stack A, the algorithm identifies its best target position in stack B
  3. Choosing optimal moves: The algorithm selects the cheapest element to move based on calculated costs
  4. Optimizing rotations: When both stacks need rotation in the same direction, the algorithm uses simultaneous operations (rr or rrr)

Video Tutorial

Watch a detailed explanation of the Push Swap algorithm and the Turkish approach

​
Key Features

​
Smart Cost Analysis

The implementation calculates the exact cost to move each element by considering:
  • Position in the current stack (above or below median)
  • Target position in the destination stack
  • Potential for simultaneous rotations
From init_a_to_b.c:64-82: 
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)
    {
        a->push_cost = a->index;
        if (!(a->above_median))
            a->push_cost = len_a - (a->index);
        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;
    }
}

​
Optimized for Different Input Sizes

  • 2 elements: Single swap operation
  • 3 elements: Specialized hardcoded sorting (max 2 operations)
  • 4+ elements: Full Turkish algorithm with cost optimization

​
Input Validation

Robust error handling for:
  • Invalid syntax (non-numeric characters)
  • Integer overflow (outside INT_MIN to INT_MAX range)
  • Duplicate numbers
  • Empty input

​
Flexible Input Format

Supports two input methods: 
# Multiple arguments
./push_swap 3 2 5 1 4

# Single quoted string
./push_swap "3 2 5 1 4"

​
Available Operations

The algorithm uses 11 stack operations:
OperationDescription
saSwap first 2 elements of stack A
sbSwap first 2 elements of stack B
sssa and sb simultaneously
paPush top of B to A
pbPush top of A to B
raRotate stack A up (first element becomes last)
rbRotate stack B up
rrra and rb simultaneously
rraReverse rotate stack A (last element becomes first)
rrbReverse rotate stack B
rrrrra and rrb simultaneously

​
Performance

The Turkish algorithm is highly efficient:
  • 100 numbers: Typically under 700 operations
  • 500 numbers: Typically under 5500 operations
These benchmarks make it one of the most competitive approaches for the Push Swap problem.

​
Data Structure

The implementation uses a doubly-linked list with rich metadata: 
typedef struct s_list
{
    int             nbr;            // The number value
    int             index;          // Current position in stack
    int             push_cost;      // Cost to move this element
    int             above_median;   // Position relative to median
    int             cheapest;       // Flag for cheapest element
    struct s_list   *target_node;   // Target position in other stack
    struct s_list   *next;
    struct s_list   *prev;
}   t_list;

​
Use Cases

  • Learning efficient sorting algorithms with constraints
  • Understanding algorithm optimization techniques
  • Practicing data structure manipulation
  • Solving competitive programming challenges
  • Teaching algorithmic thinking and cost analysis

​
Next Steps

Installation

Clone and build the project

Quick Start

Get started with basic usage

Operations Reference

Learn all available stack operations

Algorithm Deep Dive

Understand the Turkish algorithm

Build docs developers (and LLMs) love

Get started for freeTalk to us