Pancake Sort: Everyday Algorithms

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 sorting is 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:

That’s it!

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:

1. Need to order the pancakes from smallest (top) to largest (bottom), the starting stack can be arranged in any order.
2. I only can perform flip flipping the entire stack.
3. 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).
4. To order each pancake will require one flip up to the top and one flip down to its final location.

Intuitive Algorithm:

1. 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).
2. Repeat step one until the stack is ordered.
3. 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:

1. Does it work with only one pancake? – Yes
2. Does it work with two reverse order pancakes? – Yes, we flip the stack once and are done.
3. 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:

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²)
• Memory Required: O(n)

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

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)