push_swap is a C program that sorts a list of unique integers using only a limited set of stack operations (push, swap, rotate, reverse rotate) across two stacks. The challenge is efficiency — for example, sorting 500 numbers in under 5,500 operations.
I used a chunk-based algorithm, dividing the values into groups by index. First I parse and validate the input, then create a sorted copy of stack A using Selection Sort to assign each value an index. For each chunk, I find the cheapest node to move — rotating up or down depending on which costs fewer operations — and push it to stack B. Once A is empty, B is roughly sorted. To move values back, I compare the cost of pushing the top node versus the one below it, and pick whichever is cheaper.
What I learned: argument parsing and validation in C, linked list manipulation, and thinking about algorithmic efficiency in terms of operation count rather than just correctness.
What I’m proud of: writing thorough tests — edge cases, stress tests with 100 and 500 numbers, memory checks with Valgrind — and documenting them in the README.
Peer feedback:
“Great project; an optimized chunk-sort explained very well.”
— Peer evaluator, 42 London