push_swap

A stack-sorting program in C that sorts integers with a constrained instruction set, choosing moves via a cost-based algorithm to minimize total operations.

C
Algorithms
Data Structures

View GitHub All projects

~/push_swap

$ ./push_swap 5 1 4 2 3
pb
pb
ra
pa
pa
ra
$ ./push_swap $(shuf -i 1-100000 -n 100) | wc -l
570
$ ./push_swap 1 2 2
Error

Real output from building and running the public repo.

Overview

push_swap sorts an arbitrary list of integers into ascending order using only a small, constrained set of stack operations, push, swap, rotate, and reverse-rotate, across two stacks, aiming to do it in as few operations as possible rather than just correctly. Instead of a simple sort-then-translate approach, it uses a cost-based algorithm that picks the cheapest next move at every step.

Architecture

The program validates and parses its integer arguments before splitting the sorting logic across dedicated modules for the primitive stack operations, composite moves, and the core target-selection and cost-calculation loop, all driven from a single entry point. Formatted output uses a custom libftprintf implementation.

Key Features

Sorts any valid list of integers using only the allowed stack operations (pa, pb, sa, sb, ra, rb, rra, rrb, rrr)
Cost-based move selection: computes the cheapest combination of rotations on both stacks before choosing which value to move next
Input validation rejecting non-numeric input, duplicates, and out-of-range values with a clear error
Small-stack fast path that sorts the last two or three remaining elements directly instead of running the full algorithm on them

Technical Challenges

Minimizing the total number of operations rather than just producing a correct order, which meant designing a cost model instead of picking any sorting algorithm
Deciding, for every element, the cheapest combination of same-direction rotations versus split rotations across two stacks at once

Engineering Decisions

Chose a target-node strategy, where each value is assigned the closest valid position in the sorted stack, over a generic comparison sort, since the operation-count constraint rewards moves that place a value correctly on the first try
Iterated through more than one sorting approach during development before arriving at the final cost-based algorithm

Technologies Used

C, implementing the algorithm and stack operations from scratch with no external sorting libraries, verified against the 42 curriculum's checker tool for correctness and move count.

Lessons Learned

Practiced algorithmic thinking under a hard operation-count constraint, not just correctness
Learned to reason about combined cost across two coupled data structures instead of optimizing each in isolation
Improved comfort iterating on an algorithm's design once a first working version already exists