Optimal Algorithm (Puzzle 2)

At a restaurant there is a chef and his job is to cook pancakes. The problem is that he is not a good cook and as a result all the pancakes he creates are of different sizes. Now when the waiter is delivering these to the customers, he rearranges them in such a way so that the smallest one ends up at the top and the largest one at the bottom (smallest to biggest). He uses a spatula to do that. Currently the only thing that he can do to achieve that, is to grab several pancakes from the top and then flip them over so that the top pancake arrives at the bottom of the stack. The waiter can do this as many times as he wants.

The problem is to come up with an algorithm that will solve this problem i.e. after doing all that flipping, the pancakes should be sorted (smallest at the top of the stack and largest at the bottom of the stack).

I am not sure if there is a O (n^2) algorithm for this.

Thanks.

Quote:

---

Originally Posted by vsha041

I am not sure if there is a O (n^2) algorithm for this.

---

I don't know if I've misunderstood something but isn't this quite easily done in O(N)?

You can move a pancake to wherever you want it with just two flips. You insert the spatel underneath the pancake you want to move and flip over. This pancake is now at the top. Then you insert the spatel to where you want to move the top pancake and flip over and it's in the wanted place. Lets call this a 2-flip.

Now to achieve the wanted order you start with the biggest pancake and 2-flip it to the bottom (if it's not already there). Then you continue with the second biggest pancake and 2-flip it to above the biggest pancake. Etcetera.

If N is the number of pancakes they can be given any order with N 2-flips at the most and that's O(N).

Thanks for the assistance dazzle.