Talk:Pancake sorting

From Wikipedia, the free encyclopedia

Pancakes are yummy ----

This is true. Deco 22:59, 10 Apr 2005 (UTC)

Reminds me of the Tower of Hanoi problem - gtaylor.

Actually it's quite different:

• A larger pancake can be above a smaller one
• There is only one stack as opposed to 3 in tower of hanoi.

This changes the problem immensely. The bounds for towers is well known whereas the bounds for pancakes is not. -Horndude77

Not to mention that the operation of moving a pancake from one stack to another is quite different from the operation of flipping a pile of pancakes on top. But they use some of the same materials. It's sort of like the similarity between poker and cribbage. Deco 19:14, 30 Apr 2005 (UTC)

[edit] moved from main page

(Note: the discussion here and on the referencing sort algorithm page is misleading, where it suggests O(n) for the overall sort. The 2n-3 bound is only the number of flips. One still needs to figure out where to "insert the spatula", which would involve scanning the stack. So this is probably an O(n^2) or worse algorithm (not even counting the flip cost). I don't have time to fully correct this now.)

What you say is true for a Von Neumann machine as the page suggests. The operation for finding the largest pancake however could be constant time in real life. (I hope it's also obvious that the operation for flipping a stack is constant time in real live.) The best way I can think of it is looking from the top. The operation to find the biggest pancake is constant time. The pancake we need is the outermost one. We don't need to scan every pancake to find it. After we flip that one the next largest is the one that is just inside the biggest one. Again constant time. This can be repeated until the stack is sorted. This gives an overall complexity of O(n). What you are saying is true if this were implemented as a sort algorithm on a computer. This is what the page is saying, so let's leave it for now. -HornDude77

We only claim that the number of flips is linear. Any other operations aren't counted. To my knowledge no machine has ever been constructed that can do prefix reversal in constant time, so issues of practicality are moot. If you built a machine that could do this, you might as well make it able to find the maximum of a consecutive range of numbers in constant time also, which would make the sort linear-time. I'll try to incorporate some of your ideas into the article though. Deco 21:17, 2 May 2005 (UTC)