This project has been created as part of the 42 curriculum by mtran.

---

🔄 Push Swap

Sort a stack using the least number of moves possible.

---

Description

Push Swap is a project from the 42 common core. The goal is to sort a stack of integers using only a restricted set of allowed instructions, while minimizing the total number of operations.

The program works with two stacks:

• Stack A — the main stack, which must be sorted in ascending order by the end
• Stack B — a temporary auxiliary stack used to manipulate elements during the process

The challenge lies in finding the most efficient algorithm for any input size. This project introduces core concepts of algorithmic complexity and the importance of choosing the right sorting strategy depending on the number of elements.

The algorithm implemented here is a binary Radix Sort, which achieves O(n log n) complexity — an optimal trade-off between simplicity and performance given the two-stack constraint.

---

Instructions

Requirements

• git, gcc, and make available on your system

Clone the repository

git clone <repository_url> push_swap
cd push_swap

Compile

make

The Makefile compiles the main program and all internal libraries (libft + ft_printf) automatically.

Run

./push_swap 45 69 11 42 61

Arguments can also be passed as a single quoted string:

./push_swap "45 69 11 42 61"

If the input is invalid (non-integer, duplicate, out of range), the program outputs Error followed by a newline and exits.

Check the number of operations

ARG="45 69 11 42 61"; ./push_swap $ARG | wc -l

Clean build files

make clean    # removes object files
make fclean   # removes object files + binary
make re       # full recompile

---

How It Works

Allowed instructions

Instruction	Effect
sa / sb	Swap the top two elements of stack A / B
ss	sa and sb simultaneously
pa / pb	Push the top of B to A / top of A to B
ra / rb	Rotate A / B upward (top becomes bottom)
rr	ra and rb simultaneously
rra / rrb	Reverse rotate A / B (bottom becomes top)
rrr	rra and rrb simultaneously

Algorithm overview

1. Argument validation All inputs are checked for validity: integers only, no duplicates, within INT_MIN/INT_MAX. Any violation triggers an Error.

2. Indexing Each element is assigned an index corresponding to its target position in the sorted sequence. This normalizes values to a range of [0, n-1], which simplifies the binary operations.

Input : [42, 44, 46, 41, 69]
Index : [ 1,  2,  3,  0,  4]

3. Special cases For small inputs (2–5 elements), hardcoded optimal sequences are used instead of Radix Sort, as they yield fewer operations.

4. Binary Radix Sort The algorithm iterates bit by bit, from the least significant to the most significant bit of the largest index. On each pass:

• Elements with a 0 at the current bit position are pushed to stack B
• Elements with a 1 are rotated to the bottom of stack A
• All elements from B are pushed back to A

while (i <= max_bit)
{
    tmp = size;
    while (tmp-- > 0)
    {
        if ((((*stack_a)->index >> i) & 1) == 0)
            push(stack_a, stack_b, 'b');
        else
            rotate(stack_a, stack_b, 'a');
    }
    while (*stack_b)
        push(stack_a, stack_b, 'a');
    i++;
}

The outer loop runs log n times (number of bits), the inner loop processes n elements each time — giving a total complexity of O(n log n).

---

Project Structure

push_swap/
├── src/
│   ├── main.c          — entry point, argument parsing
│   ├── parsing.c       — input validation
│   ├── algos.c         — sorting algorithms (radix, small cases)
│   ├── moves.c         — all stack instructions
│   ├── linked_list.c   — stack data structure
│   ├── utils.c         — helpers
│   └── utils2.c        — additional helpers
├── libft_printf/       — custom libft + ft_printf
├── includes/
│   └── push_swap.h
└── Makefile

Resources

Algorithmic complexity

• Big-O Cheat Sheet — complexity reference for common algorithms
• Introduction to Big-O Notation — freeCodeCamp
• CS50 — Algorithms lecture — accessible introduction to sorting and complexity

Radix Sort

• Radix Sort — GeeksforGeeks — detailed explanation with examples
• Radix Sort visualization (YouTube)

Push Swap specific

• Push Swap Visualizer — graphical tool to visualize stack operations
• Push Swap Tester — automated test suite
• Medium — Push Swap explained — walkthrough of common approaches

Use of AI

• Debugging: identifying linker errors and missing symbols during compilation
• Documentation: generating and structuring this README based on project content
• Explanations: clarifying concepts around binary operations and algorithmic complexity

AI was not used to write any sorting logic, data structure code, or project implementation. All algorithm design and C code was written manually.