Unlike others sorting problem, the expensive operation is not the comparison of values, but the flipping of pancakes. In this exercise, we will explore another algorithm that attempt to reduce the amount of stack flipping. The funny side is that this algorithm was first introduced by Bill Gates, before invented Windows.
The basic idea is to grow sequences of sorted pancakes, not necessarily
starting from the bottom. We say that a sequence of ordered pancakes
constitute a block while a pancake that is not part of a block is
said to be free. The algorithm then considers the topmost pancake (of
radius t
) and search for the t+1
or
t-1
pancakes (the considered neighbor is noted
t+o
). Eight cases may happen:
t
and t+o
are free. They are
then merged in one flip.t
is free, and t+o
is the first of
a block. They are merged in one flip.t
is free but both t-1
and
t+1
are the last elements of blocks. Both blocks and
t
are merged all together in 4 flips. Beware, if either
t-1
or t+1
does not exist (because t
is 0 or max), only two flips are mandated.
t
is in a block but t+o
is
free. They are merged in one flip.t
is in a block and t+o
is the
first element of a block. They are merged in one flip.t
is in a block and t+o
is the last
element of another block. They are merged in 3 flips as follows.t
is in a block of length k+1 (the last element
is t+ko
), t+(k+1)o
is either free or the last
element of another block. Both blocks are merged in 2 flips:t
is in a block of length k+1 (the last element
is t+ko
), t+(k+1)o
is the first element of another
block (the difference with case g is that t+(k+1)o
is now the
first element of its block). Both blocks are merged in 2 flips:t
is in a block of length n
(this
block contains all pancakes). If t
is not 1, the whole stack
is fliped. The algorithm then stops.Each iteration increases the size of the blocks, so the algorithm eventually
halts in all cases. A finer analysis would show that it takes at most
(5n+5)/3
steps to sort the stack. That's better than the naïve
algorithm, that requires 2n-3 steps.
You now have almost enough information to implement this algorithm on your
own. We just have to remove the last remaining ambiguities to ensure that
you implement exactly the same algorithm that the correction. If several
cases apply to your situation, then you should use the first given one. For
example, if both cases a and b apply (e.g., with t-1
on case
a and t+1
on case b), then you should apply the
flips of case a. If a given case applies for both t+1
and t-1
, then you should apply it to t+1
.
Note that it is somehow harder than the other exercises we did so far, so don't be surprised if you need more time to achieve this. But do not give up hope, you can do it!
isFirst()
or
isFree()
. This will simplify your main algorithm afterward,
that can be written very similarly to the explication above with a bunch of
if conditions. Factorizing code this way often helps making your code more
readable.
isSelected()
returns true. It will be so only for the entity
that is currently selected in the graphical interface, that is probably the
world you are currently debugging. This will help breaking the difficulty in
parts by debugging the situation one after the other.