Question

Now suppose one side of each pancake is burned. Describe an algorithm to sort an arbitrary stack of n pancakes, so that the burned side of every pancake is facing down, using O(n) flips. Exactly how many flips does your algorithm perform in the worst case

Answer 1

B. F. (P[1..n])

for i n down to 2

k position of the ith smallest pancake

F(k) //Flip it to the top, if the top pancake’s burned side is down

F(1)

F(i) //Flip it into place, if the top pancake’s burned side is up

F(1)

The algorithm uses at most 3n-2 flips in the worst case

Explanation:

Whenever each pancake reaches the top of the stack, it will be flipped, if necessary to ensure that its burned side is up, so that whenever it is flipped down to its proper place, its burned side is down