This past week, I almost hid behind “learning.”
I was working on the push_swap project — a constrained sorting challenge where you must sort a stack of integers using only a limited set of stack operations (sa, pb, ra, etc.). No built-in sort. No shortcuts. Just operations and strategy.
Instead of building, I kept researching.
Radix sort?
Turk algorithm?
LIS-based approach?
Chunking?
I wanted the best algorithm before writing a single serious line of code.
Time was moving. I wasn’t.
Eventually, I realized something uncomfortable: I was optimizing for certainty instead of progress.
So I started building.
The Structure: Two Executables, One System
Push_swap requires two programs:
push_swap → generates sorting instructions
checker → reads instructions and verifies if the stack ends sorted
That separation is powerful.
push_swap does the thinking.
checker enforces correctness.
It forced me to design properly:
Parse CLI arguments safely
Detect duplicates
Handle both "3 2 1" and 3 2 1 formats
Exit early if already sorted
Output instructions exactly as required
It stopped being “just a sorting problem” and became a systems problem.
My Flow
I structured my program like this:
Parse input
Validate integers
Reject duplicates
Check if already sorted
Handle small cases (2–3 numbers)
Delegate large input to the Turk algorithm
For 3 elements, I hard coded permutations. Why?
Because there are only 6 possible arrangements. A general algorithm would be overkill. Optimizing small cases reduces total move count dramatically.
Then came the real decision: what algorithm to use for larger inputs.
Why I Chose the Turk Algorithm
Radix sort is simpler to implement. It’s deterministic. It works.
But push_swap scoring is based on number of moves, not time complexity alone.
Radix tends to produce more operations.
The Turk algorithm is different. It’s a greedy insertion strategy:
Push elements from stack A to stack B
Calculate the cost to insert each element back into the correct position
Choose the element with minimal rotation cost
Optimize rotations using combined operations (rr, rrr)
Instead of blindly grouping bits (like Radix), Turk evaluates cost dynamically.
It’s smarter about move count.
That mattered to me more than implementation ease.
Was it harder? Yes.
Did it force me to understand rotation cost pairing and stack state deeply? Absolutely.
But it produced better results within scoring constraints.
What I Learned Technically
Early exits matter.
Checking if the stack is already sorted saves unnecessary computation.
Small-case optimization is powerful.
Sorting 3 numbers manually is faster and cleaner than general logic.
Instruction output must be deterministic.
The checker reads from STDIN. One wrong newline breaks everything.
Algorithm choice depends on constraints.
If this were real-world production code, I’d use sort.Ints().
Here, the constraint is operations. That changes everything.
Architecture > brute force.
Separating algorithm logic into its own package made iteration easier.
What I Would Improve
If I refactor this project, I would:
Implement an LIS (Longest Increasing Subsequence) strategy to reduce pushes.
Add a post-processing compression layer to merge:
ra + rb → rr
rra + rrb → rrr
Refactor stack operations into methods for stronger cohesion.
Benchmark Turk vs Radix for 100 and 500 elements.
There is always a cleaner abstraction.
The Real Lesson
The biggest breakthrough wasn’t algorithmic.
It was mental.
I was stuck trying to choose the perfect approach before writing code.
Once I built a working version — even if imperfect — clarity followed.
Progress created insight.
Push_swap isn’t really about sorting.
It’s about thinking under constraints.
It’s about minimizing cost.
It’s about separating generation from validation.
It’s about designing small systems that behave predictably.
And most importantly:
Movement beats theoretical perfection.
Build first. Optimize second. Reflect third.
That’s the real algorithm.
Top comments (0)