Learn more about Russian war crimes in Ukraine.

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: push , pop, peek and isEmpty.

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

What can computers do? What are the limits of mathematics? And just how busy can a busy beaver be? This year, I’m writing Busy Beavers, a unique interactive book on computability theory. You and I will take a practical and modern approach to answering these questions — or at least learning why some questions are unanswerable!

It’s only $19, and you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

After months of secret toil, I and Andrew Carr released Everyday Data Science, a unique interactive online course! You’ll make the perfect glass of lemonade using Thompson sampling. You’ll lose weight with differential equations. And you might just qualify for the Olympics with a bit of statistics!

It’s $29, but you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

More by Jim

Tagged #ctci, #programming, #haskell. All content copyright James Fisher 2020. This post is not associated with my employer. Found an error? Edit this page.