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