0
$\begingroup$

I've read in most places that the minimum number of flips in the worst case scenario required to sort a stack by any algorithm is between $15n/14$ and $18n/11$. But I read here:

It was shown in the mid-1990s that we can sort any permutation (stack of unburnt pancakes) in $n-1$ reversals

that it's $n-1$. Is this wrong or have I misinterpreted the two results? Where can I see this 1990's paper which showed that it was $n-1$?

  • 0
    Yes, that's what "sliding a batch of pancakes... onto the spare plate" allows you to do: you can now reach a contiguous section arbitrarily deep into the stack and reverse it. Hang on, I should post a proper answer.2012-11-10

1 Answers 1

3

The article itself has your answer. "In the worst case, it will take between $15n/14$ and $18n/11$ flips to sort $n$ pancakes" by prefix reversals, but if you allow "sorting by reversals [of arbitrary substrings], rather than sorting by prefix reversals... we can sort any permutation (stack of unburnt pancakes) in $n-1$ reversals."

In pancake terms, when you pick up several pancakes at the top of the stack and flip them, you are performing a prefix reversal of the stack. But if have an extra plate, you can flip any contiguous section of pancakes in the middle the stack; you just slide the overlying pancakes off onto the other plate first, flip the pancakes you want, then slide the extra pancakes back on top. In other words, you can do an arbitrary (non-prefix) reversal.

  • 0
    Thanks for opening my eyes into the world of reading things carefully before doubting it :)2012-11-10