push_swap

C project · sorting, optimization

Highly optimized sorting with two stacks and a tiny set of allowed operations.

• ~560ops for 100 numbers (limit 700)
• ~5100ops for 500 numbers (limit 5500)

The problem

Sort a stack of integers using a second stack and only 11 operations (swap, push, rotate, reverse rotate), in as few operations as possible.

What I built

• Hard-coded optimal solutions for five elements or fewer.
• The Turk algorithm for anything bigger: push all but three to stack b, choosing the cheapest move each time, sort the three, then bring everything back to its right place.
• Combined moves (rr, rrr) whenever both stacks need to rotate the same way.

The hard part

Computing the real cost of each candidate move, including when rotating both stacks together saves operations, and doing it fast enough to run for every element.

Built with

• C
• Makefile
• Norminette

More projects

• metro · Lisbon metro sim in pixel art: watch the four lines run, step into any station, board a train and ride it.
• call_me_maybe · Turns a sentence into a JSON function call with a 0.6B model using constrained decoding — parseable by construction, not by luck.
• codexion · Multithreaded twist on the Dining Philosophers: coders compete for shared dongles, with FIFO/EDF scheduling.
• fly-in · Drone fleet routing: Dijkstra pathfinding, turn-based scheduling and a pygame replay.
• a-maze-ing · Maze generator with multiple algorithms, pathfinding solvers and terminal visualization.
• ft_printf · printf rebuilt from scratch: chars, strings, pointers, decimals, unsigned and hex.
• get_next_line · Reads a file descriptor one line at a time with careful dynamic memory handling.
• Libft · My own C standard library — the foundation every later 42 project is built on.