How to sort a stack using one additional stack
Question 3.6 of Cracking the Coding Interview:
Write a program to sort a stack in ascending order (with biggest items on top). You may use at most one additional stack to hold items, but you may not copy the elements into any other data structure (such as an array). The stack supports the following operations:
Imagine you’re a Turing machine, reading a tape. You have constant-time access to the tape under the machine head, but to read the tape at a far-away location, you need to scan to it.
We can model the tape using two stacks. One stack represents the tape to the left of the machine head, and one stack represents the tape to the right. The top of each stack is the value closest to the head. To move the machine head, we pop a value from one stack, and push it onto the other stack.
With this Turing-machine model of memory, how do do you sort the values in memory? One way is to do a bubble sort: move from left to right, swapping adjacent values if they’re out of order. Once we do a full sweep without any swaps, the list is sorted.
Here’s an implementation in Haskell:
module BubbleSortStacks where import Test.QuickCheck import qualified Data.List as List bubbleSort :: Ord a => [a] -> [a] bubbleSort xs = case bubble xs of (xs', True) -> bubbleSort $ rev xs' (xs', False) -> rev xs' bubble :: Ord a => [a] -> ([a], Bool) bubble xs = go (, xs, False) where go (, back:backs, swapped) = go ([back], backs, swapped) go (fronts, , swapped) = (fronts, swapped) go (front:fronts, back:backs, swapped) | front <= back = go (back:front:fronts, backs, swapped) | otherwise = go (front:back:fronts, backs, True) rev :: [a] -> [a] rev xs = go xs  where go (x:xs) ys = go xs (x:ys) go  ys = ys prop_modelcheck :: [Int] -> Bool prop_modelcheck xs = bubbleSort xs == List.sort xs main = quickCheck prop_modelcheck
More by Jim
- A probabilistic pub quiz for nerds
- Time is running out to catch COVID-19
- The inception bar: a new phishing method
- The hacker hype cycle
- Project C-43: the lost origins of asymmetric crypto
- How Hacker News stays interesting
- My parents are Flat-Earthers
- The dots do matter: how to scam a Gmail user
- The sorry state of OpenSSL usability
- I hate telephones
- The Three Ts of Time, Thought and Typing: measuring cost on the web
- Granddad died today
- Your syntax highlighter is wrong