push_swap

ProjectM2

Sort a stack of integers with two stacks and a limited set of operations in as few moves as possible.

Requires

Exam Rank 02

Unlocks

Exam Rank 03

Guide

push_swap is a milestone M2 algorithm project in C, done solo. You receive a list of distinct integers as arguments and print, on standard output, the shortest sequence of operations you can find that sorts them, using two stacks (a and b) and a fixed instruction set: sa, sb, ss, pa, pb, ra, rb, rr, rra, rrb, rrr. The grade depends on how few operations you need for 100 and 500 numbers. The bonus is a checker program that reads operations and tells whether they sort the stack.

What you will learn

Parsing and validating input: overflow, duplicates, non-numeric values
Implementing a stack with a linked list or a circular array
Complexity in terms of operations rather than CPU time
Sorting strategies under constraints: small-case hardcoding, chunking, radix sort, greedy cost-based insertion (often called the "Turk" algorithm)
Normalising values to ranks to simplify the algorithm
Writing a checker and a benchmark harness to measure yourself

Before you start

Previous nodes: Libft, and ft_printf if you want it for debugging output (the final program only writes operations).
Tools: cc, make, norminette, valgrind, and a shell loop or script to generate random permutations (shuf -i 1-1000 -n 500).
Get the official checker binary from the project page for your platform; you will use it constantly.
Decide your algorithm on paper before coding: rank normalisation plus either radix (simple, enough for a pass) or cost-based insertion (more work, better score).

Plan of attack

Day 1: parse arguments (both ./push_swap 3 2 1 and ./push_swap "3 2 1"), reject duplicates, out-of-range values and anything that is not an integer. Print Error to stderr.
Day 1: implement the stack and the eleven operations, each one printing its name.
Day 2: hardcode the cases of 2 and 3 numbers optimally, then 5 numbers by pushing the two smallest to b.
Day 3: implement the big-case algorithm. Start with radix on ranks to have something correct, then try cost-based insertion if you want the top grade.
Day 4: write a benchmark loop: 100 random runs at 100 numbers and at 500 numbers, report the maximum operation count, and pipe each run into the checker.
Day 4: optimise: merge ra plus rb into rr, pick rotation direction by cost, rotate a to its minimum at the end.
Day 5 (bonus): write checker, reading operations from stdin with your get_next_line, and printing OK or KO.
Day 5: leaks with valgrind, norminette, an already sorted input (must print nothing), and a single number.

ARG=$(shuf -i 1-10000 -n 500 | tr '\n' ' ')
./push_swap $ARG | wc -l
./push_swap $ARG | ./checker_linux $ARG

Common pitfalls

Printing operations for an already sorted list.
Accepting 2147483648, -, +, "" or 1 1.
Leaks on the error path.
An algorithm that is correct for 500 numbers but slow enough to time out the evaluator's scripts.
Optimising only the average case: the evaluator looks at the worst runs too.
A checker that blocks or crashes on an invalid instruction instead of printing Error.

How it is evaluated

Peer evaluation then Moulinette. The evaluator checks error handling, the identity cases (sorted input, no argument), and small cases (3 and 5 numbers) where the count must be very low.
For 100 numbers and 500 numbers, points depend on the number of operations. A common target for full marks is under 700 operations for 100 and under 5500 for 500, and the mandatory part needs both lists sorted every time.
The bonus checker is tested with valid, invalid and non-sorting instruction lists.
You must explain your algorithm and its operation count.

Resources