Pancake sorting

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. Unlike a traditional sorting algorithm, which attempts to sort with the least comparisons possible, 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.

The theoretically fastest algorithm has been shown to lie between (17/16)"n" and (5/3)"n" complexity, but the exact value is not known.

The simplest pancake sorting algorithm requires at most 2"n"−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 do not 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 the sort must be completed with the burnt side of every pancake down. The above simplistic algorithm also works for this problem, but some faster algorithms do not. In 2008, a group of undergraduates built a bacterial computer that can solve a simple example of the burnt pancake problem by programming "E. coli" to flip segments of DNA which are analogous to burnt pancakes. DNA has an orientation (5' and 3') and an order (promoter before coding). The bacteria report when they have solved the problem by becoming antibiotic resistant.

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.

The problem can be considered notable in cultural trivia, as the only well-known paper ever written by Microsoft Chairman and billionaire Bill Gates (as William Gates), entitled "Bounds for Sorting by Prefix Reversal" and published in 1979, describes an efficient algorithm for pancake sorting. In addition, the most notable paper published by "Futurama" co-creator David X. Cohen (as David S. Cohen) concerned the burnt pancake problem. Their collaborators were Christos Papadimitriou (then at Harvard, now at Berkeley) and Manuel Blum (then at Berkeley, now at Carnegie Mellon University), respectively.

On September 17, 2008, a team of researchers at the University of Texas at Dallas led by Founders Professor Hal Sudborough announced the acceptance by the journal "Theoretical Computer Science" of a more efficient algorithm for pancake sorting than the one proposed by Gates and Papadimitriou.The Online Encyclopedia of Integer Sequences:
* [http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A058986 Sloane's A058986] - maximum number of flips
* [http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A067607 Sloane's A067607] - number of stacks requiring the above maximum number of flips
* [http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A078941 Sloane's A078941] - maximum number of flips for a "burnt" stack
* [http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A078942 Sloane's A078942] - the number of flips for a sorted "burnt-side-on-top" stack
* [http://www.research.att.com/~njas/sequences/A092113 Sloane's A092113] - the above triangle, read by rows

References

* Gates, W. and Papadimitriou, C. [http://www.cs.berkeley.edu/~christos/papers/Bounds%20For%20Sorting%20By%20Prefix%20Reversal.pdf "Bounds for Sorting by Prefix Reversal."] "Discrete Mathematics". 27, 47-57, 1979.
* Cohen D.S. and Blum, M. "On the problem of sorting burnt pancakes." "Discrete Applied Mathematics". 61, 105-120, 1995.

External links

* [http://www.cut-the-knot.org/SimpleGames/Flipper.shtml Cut-the-Knot: Flipping pancakes puzzle] , including a Java applet for the pancake problem and some discussion.
* [http://www.math.uiuc.edu/~west/openp/pancake.html Douglas B. West's "The Pancake Problems"]
* [http://mathworld.wolfram.com/PancakeSorting.html Pancake sorting - from Mathworld]
* [http://www.research.att.com/~njas/sequences/Seis.html The Online Encyclopedia of Integer Sequences]
* [http://www.jbioleng.org/content/2/1/8 Engineering bacteria to solve the Burnt Pancake Problem]
* [http://www.bio.davidson.edu/people/kahaynes/FAMU_talk/Living_computer.swf Animation explaining the bacterial computer that can solve the burnt pancake problem.]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Sorting algorithm — In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other… …   Wikipedia

  • Topological sorting — Dependency resolution redirects here. For other uses, see Dependency (disambiguation). In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that, for every edge uv, u comes… …   Wikipedia

  • Блинная сортировка — Одна операция блинной сортировки (вариант с подгоревшими блинами) Блинная сортировка (от англ. pancake sorting)  алгоритм сортировки. Единственная операция, допустимая в ал …   Википедия

  • Tri de crepes — Tri de crêpes Le tri de crêpes (de l anglais pancake sorting) ou encore tri à la mode bretonne est une variante du problème du tri. Il s agit de trier une pile de crêpes afin que les crêpes soient empilées de la plus grande à la plus petite (au… …   Wikipédia en Français

  • Tri de crêpes — Le tri de crêpes (de l anglais pancake sorting) ou encore tri à la mode bretonne est une variante du problème du tri. Il s agit de trier une pile de crêpes afin que les crêpes soient empilées de la plus grande à la plus petite (au sens de leur… …   Wikipédia en Français

  • Merge sort — Example of merge sort sorting a list of random dots. Class Sorting algorithm Data structure Array Worst case performance O(n log n) …   Wikipedia

  • Counting sort — In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct… …   Wikipedia

  • Bogosort — Class Sorting algorithm Data structure Array Worst case performance [1] Best case performance Ω …   Wikipedia

  • Odd–even sort — Example of odd even transposition sort sorting a list of random numbers. Class Sorting algorithm Data structure Array Worst case performance …   Wikipedia

  • Cycle sort — Example of cycle sort sorting a list of random numbers. Class Sorting algorithm Data structure Array Worst case performance Θ(n2) …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”