Pancake Sorting

Posted on | In |

Many great scientific problems come from our most ordinary life, I guess.

Background and Idea

In 1975 American geometer Jacob E. Goodman brought up the following question:

The chef in our place is sloppy, and when he prepares a stack of pancakes they come out all different sizes. Therefore, when I deliver them to a customer, on the way to the table I rearrange them (so that the smallest winds up on top, and so on, down to the largest at the bottom) by grabbing several from the top and flipping them over, repeating this (varying the number I flip) as many times as necessary. If there are n pancakes, what is the maximum number of flips (as a function of n) that I will ever have to use to rearrange them?

And this is the famous pancake problem.

This is an interesting problem, because unlike array elements, pancakes cannot be swapped. What we could do is to insert spatula at any point and flip(in computer science, this is called reversal) all pancakes above it. Thus, unlike traditional sorting algorithms which focu on reducing times of comparison, here we pay more attention to times of reversals.

Below is one idea of one implementation:

  1. Find the largest pancake among all pancakes
  2. Stick a spatula into it and flip
  3. Flip the whole stack of pancakes. Now the largest pancake is at the end.
  4. Repeat 1-3 steps, now we only consider all pancakes except the last one. Keep doing it until there is no pancakes left.

Here is a video showing how it is done: Pancake Sorting

Implementation

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
class Solution{
    public void pancakeSort(int[] pancakes){
        sortHelper(pancakes, pancakes.length - 1);
    }

    private void sortHelper(int[] pancakes, int n){
        if(n == 0){
            return;
        }
        int largest = findMax(pancakes, 0, n);
        flip(pancakes, 0, largest);
        flip(pancakes, 0, n);
        sortHelper(pancakes, n - 1);
    }

    // return the index of largest pancake in current subarray
    private int findMax(int[] pancakes, int start, int end){
        int index = start;
        int max = pancakes[start];

        for(int i = start + 1; i <= end; i++){
            if(pancakes[i] > max){
                max = pancakes[i];
                index = i;
            }
        }
        return index
    }

    private void flip(int[] pancakes, int start, int end){
        int len = end - start + 1;
        for(int i = 0; i < len / 2; i++){
            swap(pancakes, start + i, end - i);
        }
    }

    // I said there is no swapping in terms of pancakes, but in current
    // computer architecture, there is no "flipping" operation, so we 
    // need to use swap to simulate it
    private void swap(int[] pancakes, int i, int j){
        int temp = pancakes[i];
        pancakes[i] = pancakes[j];
        pancakes[j] = temp;
    }
}

Reference:

Further Reading