Pancake sorting

Pancake sorting is a variation of the sorting problem in which the only allowed operation is to reverse the elements of some prefix of the sequence. The goal is to sort the sequence in as few reversals as possible. This operation can be visualized by thinking of a stack of pancakes in which one is allowed to take the top k pancakes and flip them.

Whereas in the regular sorting problem one usually seeks to minimize the number of comparisons, in pancake sorting the operation is different. Furthermore, this operation cannot be performed in constant time on a Von Neumann machine. Because of this, pancake sorting can be accomplished in a linear number of operations, which is not possible for comparison sorting. The optimal constant is known to lie between 1 and 5/3, but the exact value is not known.

The simplest pancake sorting algorithm requires at most 2n-3 flips. In this algorithm, a variation of selection sort, we bring the largest pancake not yet sorted to the top with one flip, and then take it down to its final position with one more, then repeat this for the remaining pancakes. Note that we don't count the time needed to find the largest pancake, only the number of flips; if we wished to create a real machine to execute this algorithm in linear time, it would have to both perform prefix reversal (flips) and be able to find the maximum of a range of consecutive numbers in constant time.

In a more difficult variation called the Burnt Pancake Problem, the bottom of each pancake in the pile is burnt, and we must complete the sort with the burnt side of every pancake down. The above simplistic algorithm also works for this problem, but some faster algorithms do not.

Although seen more often as an educational device, pancake sorting also appears in applications in parallel processor networks, in which it can provide an effective routing algorithm between processors.

As an interesting piece of trivia, the only well-known paper ever published by Microsoft Chairman and billionaire Bill Gates, entitled "Bounds for Sorting by Prefix Reversal," describes an efficient algorithm for pancake sorting.

Related Integer Sequences

The following describes the number of flips per specified stack height. the first number is the height of the pancake stack. The following numbers are the number of stacks of that height that require 0, 1, 2, . . . flips to get back to the starting stack.

• 1 - 1
• 2 - 1 1
• 3 - 1 2 2 1
• 4 - 1 3 6 11 3
• 5 - 1 4 12 35 48 20
• 6 - 1 5 20 79 199 281 133 2
• 7 - 1 6 30 149 543 1357 1903 1016 35
• 8 - 1 7 42 251 1191 4281 10561 15011 8520 455
• 9 - 1 8 56 391 2278 10666 38015 93585 132697 79379 5804
• 10 - 1 9 72 575 3963 22825 106461 377863 919365 1309756 814678 73232
• 11 - 1 10 90 809 6429 43891 252737 1174766 4126515 9981073 14250471 9123648 956354 6
• 12 - 1 11 110 1099 9883 77937 533397 3064788 14141929 49337252 118420043 169332213 111050066 13032704 167

Sequences from The Online Encyclopedia of Integer Sequences:

• Sloan's A058986 (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A058986)
• Sloan's A067607 (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A067607)
• Sloan's A078941 (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A078941)
• Sloan's A078942 (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A078942)

References

• Gates, W. and Papadimitriou, C. "Bounds for Sorting by Prefix Reversal." Discrete Mathematics. 27, 47-57, 1979.

External links

• The Online Encyclopedia of Integer Sequences (http://www.research.att.com/~njas/sequences/Seis.html)
• Douglas B. West's "The Pancake Problems" (http://www.math.uiuc.edu/~west/openp/pancake.html)
• Pancake sorting - from Mathworld (http://mathworld.wolfram.com/PancakeSorting.html)