This project has been created as part of the 42 curriculum by vneves-c, jpaulo-p.

push_swap

Description

push_swap sorts a list of integers using two stacks (a and b) and a limited instruction set (sa, sb, ss, pa, pb, ra, rb, rr, rra, rrb, rrr). The program prints to standard output the sequence of operations that sorts stack a in ascending order.

What makes this version of the project special is that the binary embeds four distinct sorting strategies, selectable at runtime, and an adaptive mode that measures how disordered the input is before choosing how to sort it:

Flag	Strategy	Complexity (in generated ops)
--simple	Selection sort by minimum	O(n²)
--medium	Chunk sort	O(n·√n)
--complex	LSD binary radix sort	O(n·log n)
--adaptive	Disorder-based dispatcher	Depends on measured disorder

--adaptive is the default when no flag is given. A fifth flag, --bench, can be combined with any of the above to print metrics on standard error.

Instructions

Requirements

• Linux or macOS with cc and make
• Our libft and ft_printf, copied into ./libft/ and ./printf/ (both are built automatically by the project Makefile)

Compilation

make            # builds ./push_swap
make clean      # removes objects
make fclean     # removes objects, libraries and the binary
make re         # full rebuild
make norm       # runs norminette on srcs, includes, libft and printf

Usage

# Default (adaptive) strategy
./push_swap 2 1 3 6 5 8

# Force a specific strategy
./push_swap --simple 5 4 3 2 1
./push_swap --complex 4 67 3 87 23

# Count operations
ARG="4 67 3 87 23"; ./push_swap --adaptive $ARG | wc -l

# Verify the output with the checker provided by the school
ARG="4 67 3 87 23"; ./push_swap --complex $ARG | ./checker_linux $ARG

# Benchmark mode: metrics go to stderr, operations stay on stdout
shuf -i 0-9999 -n 500 > args.txt
./push_swap --bench $(cat args.txt) 2> bench.txt | ./checker_linux $(cat args.txt)
cat bench.txt

Benchmark output looks like this:

[bench] disorder: 49.93%
[bench] strategy: Adaptive / O(n log n)
[bench] total_ops: 6784
[bench] sa: 0  sb: 0  ss: 0  pa: 3392  pb: 3392
[bench] ra: 0  rb: 0  rr: 0  rra: 0  rrb: 0  rrr: 0

Errors (non-integers, values outside int range, duplicates) print Error on standard error. With no parameters, the program prints nothing and returns the prompt.

The benchmark block is written to file descriptor 2 precisely so that the operation stream on file descriptor 1 stays clean and can still be piped into the checker.

Algorithms and justification

Value normalization (ranks)

Right after parsing, every value is replaced in memory by its rank: the smallest value becomes 0, the next one 1, ..., up to n-1. Sorting the ranks requires exactly the same operation sequence as sorting the original values, because all our decisions depend only on relative order — which the transformation preserves.

Why we do it:

• Radix sort works on non-negative integers only; ranks remove negatives for free.
• Ranks cap the number of radix passes at ⌈log₂ n⌉ (9 passes for 500 numbers) instead of up to 31 passes for raw int values.
• Chunk boundaries become trivial: a chunk is simply a rank interval.

The O(n²) double loop that computes ranks runs in C and costs zero push_swap operations — and the subject's complexity model counts generated operations only.

Disorder metric

Disorder is the fraction of inverted pairs (a bigger number appearing before a smaller one) over all possible pairs, giving a number in [0, 1] — 0 for a sorted stack, 1 for a reversed one. It is computed with the exact pseudocode from the subject, before any move.

To avoid floating-point arithmetic entirely, the value is stored as an integer scaled by 10000: a disorder of 0.4993 is stored as 4993. The subject's thresholds of 0.2 and 0.5 therefore become integer comparisons against 2000 and 5000, and --bench recovers the two decimals with a division and a remainder. The accumulators are declared long because mistakes * 10000 reaches roughly 1.25 × 10⁹ for 500 elements, which is uncomfortably close to the int ceiling.

--simple — Selection sort by minimum, O(n²)

Find the position of the smallest element still in a, rotate it to the top through the shortest direction (ra or rra), push it to b; repeat, then push everything back with pa. Since elements enter b in ascending order, they come back to a sorted with the smallest on top.

• Ops upper bound: each of the n extractions costs at most n/2 rotations + 1 push, plus n final pa → O(n²).
• Space: the two stacks plus O(1) auxiliary variables → O(n).
• Why this one: it is the most natural fit for the stack model (one reusable primitive: "locate and rotate to top") and easy to reason about during defense.

--medium — Chunk sort, O(n·√n)

Phase 1 walks stack a pushing values to b in chunk order: if the top of a belongs to the current chunk, pb (plus an extra rb when the value sits in the lower part of the chunk, which keeps larger values near the top of b); otherwise ra. Phase 2 repeatedly rotates the maximum of b to its top through the shortest direction and brings it back with pa.

Chunk sizing. The chunk width is chosen empirically rather than computed as ⌈√n⌉: 20 for n ≤ 100, 40 above. For n = 100 this yields 5 chunks (√100 = 10 would give 10), and for n = 500 it yields about 12 chunks (√500 ≈ 22). We tuned these two values by measurement — wider chunks reduce the number of scanning passes over a at the cost of more rotations inside b, and the tested sizes landed at a better operation count than the textbook √n split. The asymptotic behaviour is unchanged: with a chunk count k, phase 1 costs O(n·k) and phase 2 costs O(n²/k), which is the O(n·√n) family for any k proportional to √n; our fixed widths sit inside that regime for the input sizes the subject benchmarks.

• Ops upper bound: phase 1 scans a once per chunk → O(n·√n); phase 2 extractions stay cheap because each chunk keeps its larger elements near the top of b → O(n·√n) overall.
• Space: O(n) for the stacks, O(1) extra.
• Why this one: it reuses the "locate and rotate to top" primitive from --simple and only adds a bucketing pre-pass, so it is the smallest step up in code complexity.

--complex — LSD binary radix sort, O(n·log n)

For each bit from the least significant to bit ⌈log₂ n⌉−1 of the rank: scan the whole stack a; if the current bit of the top element is 0, pb, otherwise ra. After the scan, pa everything back and move to the next bit.

The bit is extracted with (value >> b) & 1, and the number of passes comes from count_bits(size - 1) — the width of the largest rank. Because each pb shrinks a during the scan, the stack size is captured before the inner loop so that every element is examined exactly once per pass.

• Ops upper bound: each of the ⌈log₂ n⌉ passes costs n scan operations plus at most n pa → ≤ 2n·⌈log₂ n⌉ = O(n·log n).
• Space: O(n) for the stacks, O(1) extra.
• Why this one: no comparisons, no recursion, no pivot handling — by far the simplest correct O(n·log n) strategy in the two-stack model, and its operation count is fully deterministic for a given n.

--adaptive — Disorder-based dispatcher (default)

The adaptive strategy measures the disorder of the initial stack and delegates to the strategy whose cost profile fits that regime, using the thresholds fixed by the subject:

Regime	Condition	Delegates to	Bound
Low	disorder < 0.2	--simple	O(n²)
Medium	0.2 ≤ disorder < 0.5	--medium	O(n·√n)
High	disorder ≥ 0.5	--complex	O(n·log n)

Threshold rationale: the thresholds are mandated by the subject, and they match the algorithms' behaviour reasonably well. A nearly sorted stack has few inversions, so the selection method finds most minima near the top and performs far fewer rotations than its worst case suggests. A moderately shuffled stack still has local structure that chunking exploits. A heavily shuffled stack has no structure left, so the deterministic radix bound is the safest choice.

Complexity argument: each regime delegates to a strategy whose upper bound (proved in the sections above) is exactly the bound required for that regime, so the adaptive strategy satisfies the per-regime targets by construction. Space stays O(n) in every regime.

An honest observation. Uniformly random input has a disorder close to 0.5 (we measured 42% – 53% across samples of 100 numbers), so --adaptive lands on the high-disorder branch most of the time and runs the radix sort. As the measured table below shows, our chunk sort is actually cheaper than radix at both benchmark sizes — so following the subject's thresholds does not always select the strategy with the lowest operation count. We kept the mandated thresholds because the project specifies them, but the measurement is worth stating: asymptotic class and real operation count are not the same thing at n = 100 or n = 500.

Small inputs

Inputs of size 2, 3, 4 and 5 are handled by dedicated routines (sort_two, sort_three, sort_four, sort_five) regardless of the selected strategy flag, since asymptotic classes are meaningless at that scale. sort_three enumerates the six possible arrangements and resolves each in at most two operations; sort_four and sort_five push the smallest one or two elements to b, sort the remaining three, and push them back. A stack that is already sorted returns immediately with zero operations, at any size.

Benchmark results

Averages over 10 runs with distinct random inputs, measured with the default (--adaptive) strategy:

Input size	Strategy	Avg ops	Target (pass / good / excellent)
100	--adaptive	802	2000 / 1500 / 700
500	--adaptive	5962	12000 / 8000 / 5500

Measured comparison between strategies

Same inputs, same methodology, forcing each strategy:

Input size	--simple	--medium	--complex	--adaptive
100	1484	609	1084	802
500	32508	5156	6784	5962

Three things worth noting during defense:

• --medium beats --complex at both sizes, despite having the worse asymptotic class. Chunk sort's constant factor is small, and n = 500 is far from the range where O(n·log n) starts to dominate O(n·√n).
• --simple exceeds the 12000-operation limit at n = 500 (32508 operations). That is the expected behaviour of a quadratic method and precisely why the adaptive dispatcher never selects it for high disorder.
• --adaptive sits between medium and complex, because it mixes the two depending on the measured disorder of each individual input.

Reproducing the tests

The repository includes test_push_swap.sh, a shell script covering 43 checks: error handling (non-integers, duplicates, INT overflow, empty strings), empty output cases, all six permutations of three elements, sizes from 4 to 500, all four strategy flags, eight hand-computed disorder values, and verification that the benchmark block never leaks into standard output.

chmod +x test_push_swap.sh
./test_push_swap.sh

The script expects the school's checker binary in the project root, named checker_linux (or checker_Mac on macOS — adjust the CK variable at the top).

Team and contributions

Learner	Main contributions
vneves-c	Argument parsing and validation, stack allocation and filling, flag handling, --simple and --medium strategies, shared stack utilities
jpaulo-p	Stack primitives and the eleven operations, rank normalization, disorder metric, small-input routines, --complex (radix), --adaptive, benchmark mode

Both learners reviewed each other's code and can explain every part of the project.

Resources

• Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching
• Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (chapters on sorting and lower bounds)
• Wikipedia: Sorting algorithm, Radix sort, Inversion (discrete mathematics)
• man pages: read(2), write(2), malloc(3), free(3), exit(3)

How AI was used

AI (Anthropic's Claude) was used for:

• Discussing which algorithm families best fit each required complexity class and the trade-offs between them (no algorithm code was generated).
• Generating the initial project skeleton: this README.md draft, the Makefile, header skeletons, .gitignore, and the benchmark script in tools/.