This project has been created as part of the 42 curriculum by gvoelkne, jkrishna.

push_swap#

Description#

push_swap sorts a sequence of integers using exactly two stacks (a and b) and a fixed set of operations, printing the shortest operation sequence it can find to stdout. The program implements four distinct sorting strategies — Simple, Medium, Complex, and Adaptive — and selects among them based on a runtime flag or, by default, by measuring how disordered the input is.

The project was completed as a group by:

Instructions#

Build

make        # produces ./push_swap
make re     # clean rebuild

Run

# default (adaptive strategy)
./push_swap 5 4 3 2 1

# force a specific strategy
./push_swap --simple  5 4 3 2 1
./push_swap --medium  5 4 3 2 1
./push_swap --complex 5 4 3 2 1

# verify correctness with the provided checker
ARG="4 67 3 87 23"; ./push_swap --complex $ARG | ./checker_linux $ARG

# benchmark output (disorder %, strategy name, op count and breakdown) on stderr
./push_swap --bench 5 4 3 2 1

Numbers may be passed as separate arguments or as a single quoted string ("5 4 3 2 1"). Passing no numbers prints nothing. Invalid input (non-integers, out-of-range values, duplicates) prints Error to stderr and exits with status 1.

Algorithms#

Disorder metric#

Before any sorting begins the program computes a disorder value in [0, 1]: the fraction of pairs (i, j) with i < j where a[i] > a[j] (i.e. the normalised inversion count). A disorder of 0 means the stack is already sorted; 1 means it is in reverse order.

Simple — Insertion Sort · O(n²)#

The minimum element of stack a is located, the stack is rotated so that element sits on top (using ra or rra, whichever is shorter), and it is pushed to b. This repeats until two elements remain in a, which are swapped if needed with sa. All of b is then pushed back to a with pa.

Each "find-and-push" pass costs at most n/2 rotations; doing this n times gives O(n²) operations.

Why use it for low disorder (< 0.2)? A nearly-sorted stack has very few inversions. Insertion sort degrades gracefully: when the minimum is already near the top, the rotation cost is small, so the real operation count is much closer to O(n) than the theoretical worst case.

Medium — Chunk Sort · O(n√n)#

Elements are assigned a rank from 0 (smallest) to n−1 (largest). The rank space is split into chunks of size ≈ 5√n. For each chunk, stack a is scanned: any element whose rank falls in the current range is pushed to b immediately; elements outside the range are rotated past (choosing ra or rra to minimise moves). Once all chunks are pushed, stack b holds elements in roughly descending rank order.

b is then drained back to a greedily: on each step, every element in b is considered as a candidate, its combined rotation cost to become the next element inserted into a at the correct position is computed, and the cheapest candidate is moved.

There are n/chunk_size ≈ √n chunks. Within each chunk, each element requires at most O(√n) rotations on average to reach the top (elements are spread uniformly, so expected distance ≈ chunk_size/2 ≈ √n/2). Total push phase: n × O(√n) = O(n√n). The greedy pull-back phase is also empirically O(n√n).

Why use it for medium disorder (0.2–0.5)? With a moderately shuffled stack, chunk sort's chunk-based locality keeps rotation costs low without needing the full overhead of a bit-by-bit radix pass.

Complex — LSD Radix Sort · O(n log n)#

Elements are assigned ranks 0–(n−1). The sort processes the binary representation of each rank from the least-significant bit upward. In each pass, every element in a is inspected: if the current bit is 0 the element is pushed to b; if it is 1 it is rotated to the back of a. After all n elements are processed, everything in b is pushed back to a. After log₂(n) passes the ranks are in ascending order in a.

Each of the log₂(n) passes costs exactly 2n operations (n push/rotate + n push-back), giving O(n log n) total.

Why use it for high disorder (≥ 0.5)? Highly randomised input invalidates any locality assumption. Radix sort's cost depends only on n and the number of bits — it is immune to disorder and scales reliably.

Adaptive — disorder-based dispatch#

Threshold rationale. 0.2 is the point above which a nearly-sorted assumption no longer holds and the O(n²) constant becomes dominant. 0.5 marks the midpoint of disorder where chunk locality degrades enough that the guaranteed O(n log n) of radix sort becomes cheaper in practice. Both thresholds were validated empirically against the 100- and 500-element benchmarks.

Space complexity. All strategies use stack b as auxiliary storage (O(n) nodes) and O(1) additional variables. No extra arrays are allocated.

Resources#

• youtube: radix sort, linked lists
• Wikipedia: Insertion sort, Radix sort
• 42 community push_swap visualiser: https://github.com/o-reo/push_swap_visualizer

AI usage. Claude Code (Anthropic) was used throughout the project:

• Explaining Big-O analysis for the chunk sort and radix sort variants in the push_swap operation model (i.e., counting operations rather than comparisons).
• Drafting documentation.

All AI-generated content was reviewed, tested, and understood by both group members before being accepted into the project.