Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
1  
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." –  Rahul Nov 8 '12 at 1:31
    
@RahulNarain Oops, didn't read that too carefully. So that's if you reverse any contiguous section in the stack? –  asymptotically Nov 8 '12 at 1:43
    
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. –  Rahul Nov 10 '12 at 2:18
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
Thanks for opening my eyes into the world of reading things carefully before doubting it :) –  asymptotically Nov 10 '12 at 5:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.