push_swap

A sorting program written in C as part of the 42 school curriculum. Given a list of integers, push_swap outputs the shortest sequence of operations needed to sort them in ascending order using two stacks and a limited instruction set.

Note: No AI was used during the development, research, or implementation of this project. AI was only used for the redaction of this README.

---

The Problem

You have two stacks, A and B. Stack A starts loaded with an unsorted list of unique integers. Stack B starts empty. The goal is to sort all numbers into stack A in ascending order using the fewest possible operations.

The only allowed operations are:

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

---

How It Works

Data Structures

Each element in a stack is a node in a singly linked list (t_stack). Beyond its value (nbr), each node tracks:

• index — its position from the top of its stack
• moves — the total cost (in operations) to bring it to the top
• target — a pointer to the node in stack A it should land on top of when pushed back

A global control structure (t_val) holds metadata: stack sizes, the global median, pointers to the minimum and maximum nodes, and median indices for both stacks.

Sorting Strategy

The solver dispatches to different algorithms depending on input size:

2 or 3 elements

Direct, hardcoded logic. For 2 elements, swap if out of order. For 3 elements, the maximum is rotated out of the way, then a conditional swap finishes the sort. Always 2 operations or fewer.

4 or more elements — the main algorithm (chechen_sort)

A greedy, cost-minimizing algorithm that works in two phases:

Phase 1 — Migration to stack B: All but 3 elements are pushed from A to B. To pre-sort B and reduce work later, elements above the median are rotated to the bottom of B immediately after being pushed. This splits B into a rough upper half (larger values) and lower half (smaller values).

Phase 2 — Reinsertion into stack A: For each element remaining in B, the algorithm:

1. Assigns a target in stack A — the closest larger number above it (or the minimum if none exists, to maintain the circular sorted order).
2. Computes the cost to bring both the B element and its target to the top of their respective stacks. When both elements are on the same side of their stack's median, a simultaneous rr or rrr operation halves the cost; otherwise costs are summed.
3. Selects the cheapest element in B and executes the rotations to align it with its target, exploiting simultaneous rotations whenever possible.
4. Pushes it onto A with pa.

After all elements are back in A, the stack is sorted except that the minimum may not be at the top. A final rotation (chosen by direction based on which is shorter) brings the minimum to the top, completing the sort.

Parsing

Arguments are accepted as multiple separate arguments or as a single space-separated string (or any mix). The parser walks each argument character by character, validates that only digits, signs (+/-), and whitespace appear, extracts integers using a custom atoi that catches INT overflow and underflow, and rejects empty arguments, bare signs, or duplicate values. A sorted copy of the input array is used for the duplicate check and to compute the global median, then freed immediately.

---

The Checker (Bonus)

The checker binary reads a sequence of operations from stdin and applies them to the same initial stack. It prints OK if the stack ends up sorted with stack B empty, and KO otherwise.

---

Building

Requirements: a C compiler (cc) and make.

# Build push_swap only
make

# Build checker only
make bonus

# Build both
make both

# Clean object files
make clean

# Remove all build artifacts and binaries
make fclean

# Full rebuild
make re

---

Usage

# Sort a list of numbers
./push_swap 4 2 7 1 5

# Pipe output into checker to verify correctness
./push_swap 4 2 7 1 5 | ./checker 4 2 7 1 5

# Generate and test a random 500-element permutation
ARG=$(seq 500 | shuf | tr '\n' ' ')
./push_swap $ARG | ./checker $ARG

# Count the number of operations produced
ARG=$(shuf -i 0-10000 -n 100 | tr '\n' ' ')
./push_swap $ARG | wc -l

Error cases — the program writes Error to stderr and exits on:

• Non-integer arguments
• Integer overflow or underflow
• Duplicate values
• Empty or bare-sign arguments (+, -)

---

Project Structure

.
├── include/
│   ├── push_swap.h       # Main header: structs and all function prototypes
│   └── checker.h         # Checker-specific header
├── src/
│   ├── main.c            # Entry point for push_swap
│   ├── checker_main.c    # Entry point for checker
│   ├── checker_utils.c   # Operation dispatcher and result printer
│   ├── solver.c          # Algorithm dispatcher, sort_two, sort_three
│   ├── chechen_sort.c    # Core sorting algorithm (4+ elements)
│   ├── intel_gathering.c # Cost computation and min/max tracking
│   ├── jade.c            # Target node resolution, final A rotation
│   ├── parsing.c         # Stack construction from argv
│   ├── error_check.c     # Validation, duplicate detection
│   ├── int.c             # atoi with overflow check, median, min/max helpers
│   ├── array.c           # Stack-to-array copy
│   ├── quicksort.c       # In-place quicksort (used for duplicate check)
│   ├── lst_functions.c   # Linked list primitives for t_stack
│   ├── push.c            # pa, pb
│   ├── swap.c            # sa, sb, ss
│   ├── rotate.c          # ra, rb, rr
│   └── reverse_rotate.c  # rra, rrb, rrr
└── lib/
    └── libft/            # Custom C standard library

---

Author

akdovlet — 42 school