push_swap

C project · sorting, optimization

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

• 561ops on average for 100 numbers (limit 700)
• 632at worst over 1000 runs
• 5118ops on average for 500 numbers (limit 5500)
• 5413at worst over 300 runs

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

• A hard-coded case for each order of three numbers; four or five are sorted by pushing the smallest to b, sorting the three left and pushing back.
• 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.
• A visualizer that runs in the browser: this same C compiled to WebAssembly, every operation it prints replayed on two stacks of bars, step by step or all at once.

The hard part

Counting what each candidate move really costs. Bringing a number to the top of a and its target to the top of b normally costs both rotations added up, but when both sit in the same half of their stack, rr or rrr do them together and the cost is only the larger one. Scoring every number in a this way before each push keeps 500 numbers at 5118 operations on average, 5413 at worst over 300 random runs, under the 5500 limit.

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.
• pac-man · Pac-Man in Python, built as a duo with sylvzzz: a new maze every level and four ghosts that each hunt you differently.
• 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.
• dbaltaza.pt · A game-console portfolio where every project is a pre-rendered disc: Vite + TypeScript, no framework, and a paint budget the tests measure.
• 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.