Personally, I find algorithms related to the world around us interesting and fun. The Pancake Sorting problem is a classic example and introduced in many algorithms courses. If this is your first time coming in contact with this problem I *highly* recommend trying to come up with your own solution upon reading the description. Hope you enjoy, Everyday Algorithms: Pancake Sort!

### Pancake Sorting

From wikipedia:

Pancake sortingis the colloquial term for the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it.

Simply put, we have a spatula and a stack of pancakes. The goal is to order the pancakes from largest on the bottom, to smallest on the top. The only caveat being we can only action we can preform is *flip* which is preformed by inserting the spatula and flipping the entire stack above the spatula over. For demonstration purposes, we first start off with any old stack of pancakes:

We then decide where to insert the spatula:

The red arrow represents the insertion point, the blue represents what will be the new bottom of the stack (once it has been flipped). Then, we just flip the stack:

### Pancake Sorting Algorithm

Prior to reviewing this solution, I recommend trying to do this on your own.

This is by no means the best solution, but it is the most straight forward and easiest to explain. I chose to present this solution because I believe it will provide insight as to how “easy” and intuitive some of these algorithms can be and I hope to convince people to “take a stab” at trying algorithms themselves. Often computer science majors/professors can scare off people outside their field by being too intense at first. At the end of this solution I will provide links to other, *quicker* solutions.

Dissecting the problem:

- Need to order the pancakes from smallest (top) to largest (bottom), the starting stack can be arranged in any order.
- I only can perform
*flip*flipping the entire stack. - To flip a specific pancake to the bottom of the stack, we first must flip it to the top (then flip it again to the bottom).
- To order each pancake will require one flip up to the top and one flip down to its final location.

Intuitive Algorithm:

- Find the largest
*out of order*pancake and flip it to the bottom (you may need to flip it to the top of the stack first). - Repeat step one until the stack is ordered.
- That’s it, a two step algorithm will work.

Now that we have an algorithm, lets test it out mentally on a few edge cases:

- Does it work with only one pancake? – Yes
- Does it work with two reverse order pancakes? – Yes, we flip the stack once and are done.
- Does it work with three pancakes where we have the following order: medium, large, small? – Yes, we flip the large to the top and obtain: large, medium small. We then slide the spatula under the small pancake and flip the whole stack: small, medium, large.

Since those test cases seemed to work out just fine, I took the liberty of coding this up in python.

Feel free to fork it from my github:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
# Sorts Pancakes def sortPancakes(stack): sorted_index = 10 for i in reversed(range(len(stack))): stack = flip(stack, findLargestPancake(stack, i)) print("Flip Up", stack) stack = flip(stack, i) print("Flip Down", stack) return stack # All of the pancakes are sorted after index # Returns the index of largest unsorted pancake def findLargestPancake(stack, index): largest_pancake = stack[index] largest_index = index; for i in range(index): if stack[i] > largest_pancake: largest_pancake = stack[i] largest_index = i print "" print("Insert Spatula in index", largest_index, "Size", largest_pancake) return largest_index # Slide spatula under pancake at index and flip to top def flip(stack, index): newStack = stack[:(index + 1)] newStack.reverse() newStack += stack[(index + 1):] return newStack stack = [1, 4, 5, 2, 3, 8, 6, 7, 9, 0] print"\nUnsorted:" print stack print "\nIterating:" stack = sortPancakes(stack) print "\nSorted:" print stack print "" |

**Output for Pancake Sort:**

Unsorted: [1, 4, 5, 2, 3, 8, 6, 7, 9, 0]

Iterating:

(‘Insert Spatula in index’, 8, ‘Size’, 9)

(‘Flip Up’, [9, 7, 6, 8, 3, 2, 5, 4, 1, 0])

(‘Flip Down’, [0, 1, 4, 5, 2, 3, 8, 6, 7, 9])

(‘Insert Spatula in index’, 6, ‘Size’, 8)

(‘Flip Up’, [8, 3, 2, 5, 4, 1, 0, 6, 7, 9])

(‘Flip Down’, [7, 6, 0, 1, 4, 5, 2, 3, 8, 9])

(‘Insert Spatula in index’, 0, ‘Size’, 7)

(‘Flip Up’, [7, 6, 0, 1, 4, 5, 2, 3, 8, 9])

(‘Flip Down’, [3, 2, 5, 4, 1, 0, 6, 7, 8, 9])

(‘Insert Spatula in index’, 6, ‘Size’, 6)

(‘Flip Up’, [6, 0, 1, 4, 5, 2, 3, 7, 8, 9])

(‘Flip Down’, [3, 2, 5, 4, 1, 0, 6, 7, 8, 9])

(‘Insert Spatula in index’, 2, ‘Size’, 5)

(‘Flip Up’, [5, 2, 3, 4, 1, 0, 6, 7, 8, 9])

(‘Flip Down’, [0, 1, 4, 3, 2, 5, 6, 7, 8, 9])

(‘Insert Spatula in index’, 2, ‘Size’, 4)

(‘Flip Up’, [4, 1, 0, 3, 2, 5, 6, 7, 8, 9])

(‘Flip Down’, [2, 3, 0, 1, 4, 5, 6, 7, 8, 9])

(‘Insert Spatula in index’, 1, ‘Size’, 3)

(‘Flip Up’, [3, 2, 0, 1, 4, 5, 6, 7, 8, 9])

(‘Flip Down’, [1, 0, 2, 3, 4, 5, 6, 7, 8, 9])

(‘Insert Spatula in index’, 2, ‘Size’, 2)

(‘Flip Up’, [2, 0, 1, 3, 4, 5, 6, 7, 8, 9])

(‘Flip Down’, [1, 0, 2, 3, 4, 5, 6, 7, 8, 9])

(‘Insert Spatula in index’, 0, ‘Size’, 1)

(‘Flip Up’, [1, 0, 2, 3, 4, 5, 6, 7, 8, 9])

(‘Flip Down’, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

(‘Insert Spatula in index’, 0, ‘Size’, 0)

(‘Flip Up’, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

(‘Flip Down’, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

Pancake Sort Completed!

Sorted:* *[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

It works! It was really that simple.

### Calculating Runtime

Calculating the runtime of an algorithm is important, it allows you to know the *complexity* and in turn *scalability* of the problem. In computer science we often use Big-O notation, which basically means the “bounds” on the running time (if you don’t recall or have never learned this notation I recommend reading the wikipedia article).

Analyzing the runtime of this algorithm is pretty straight forward. In the worst case the stack will be alternating smallest to largest as so: [0, 9, 1, 8, 2, 7, 3, 6, 5, 4]. In this case we will have to flip 9 to the top, then to the bottom, or two flips. We then continue with 8, 7, 6, etc. each one requiring two flips to get the pancake to its final *sorted* location. Meaning it will take a maximum 2n – 3 *flips*, n being the number of pancakes in the stack and “-3″ because the final pancake will be in the appropriate position after the second to last flip and the second to last flip will only occur once (no need to flip up then down). Based on some of the Reddit comments, to avoid confusion I am appending that I ignore “searching time” in the complexity calculations and I’ll first base runtime off *flips.*

n: number of pancakes in stack

- Run Time (based on flips): O(n)
- Memory Required: O(n)

However, this does not take into consideration the time it takes the search the stack for the largest pancake. In my implementation above, in order to find the largest pancake (prior to flipping) we must search the entire (unsorted) stack. This gives us a “worst case” runtime of n (the total number of pancakes) times n, because we have to run through the whole stack to find the largest, making the total runtime:

n: number of pancakes in stack

- Run Time (based on flips): O(n
^{2}) - Memory Required: O(n)

I should also note in my program does use more than “n” memory:

1 2 3 4 5 6 |
# Slide spatula under pancake at index and flip to top def flip(stack, index): newStack = stack[:(index + 1)] newStack.reverse() newStack += stack[(index + 1):] return newStack |

My solution would have require O(n + k) memory, k being the size of the first stack flip, with a bound on n – 1. Making my solution have an upper bound on memory usage of 2n – 1 or O(n). If we wished to avoid this we could *flip* all the values in place, swapping values all the way down the array, but that would just detract from readability.

### Closing Remarks

The above algorithm is not the *quickest* solution and if you are interested in reading about this problem further, I recommend reading this paper by Bill Gates and Christos Papadimitriou as well as this paper by Chitturi, Fahle, Meng (and some more guys). I also recommend reading my article on counting sort, if you enjoyed this article!

I will be releasing a walk through for the more difficult “Burnt Pancake Problem” in which:

The bottom of each pancake in the pile is burnt, and the sort must be completed with the burnt side of every pancake down.

This solution was released via my mailing list, which you can view:

Exclusive Content, Updates and Links for June 2014

##### Related Articles

- Counting Sort in C
- Introduction to Linear Regression
- Introduction to Markov Processes
- I/O Multiplexing Using epoll and kqueue System Calls
- Intro to IPC | Inter Process Communication

##### Recommended Reading

- Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein)
- Algorithms (Jeff Erickson)
- Introduction to Theory of Computation (Sipser)

I’ll be honest, I barely understand what I just read, but you’ve made me crave pancakes!

The parts I understood were interesting, and I’ll read anything that involves pancakes! You said to try it on my own, so I made pancakes, and by the time I was done flipping them they were a big mess. I guess my spatula isn’t big enough. (just kidding about all that!)

It was good for my brain to do some problem solving today.

Actually since this is an everyday algorithm you do not necessarily wish to sort the pancakes by largest to smallest because that may be inefficient. You would wish to sort it by how efficient it will be to serve and select the number (n) of pancakes requested by the person consuming the pancake. Eg: You could rest unevenly stacked pancakes together if the next number of pancakes by person #2 wouldn’t impact the selection.

Easy peasy. It’s there an algorithm that’s better than quadratic?