Pancake sorting is a sorting algorithm . The only operation allowed in the algorithm is the flipping of sequence elements to an index. Unlike traditional algorithms, which minimize the number of comparisons, in pancake sorting you need to make as few flips as possible. The process can be visually represented as a stack of pancakes , which is shuffled by taking a few pancakes from above and turning them over.
Content
Algorithm
The simplest algorithm ( sorting option by choice ) gives no more than coups, however, requires the search for the largest element [1] . In 1979, Bill Gates and Christ Papadimitriou presented their algorithm and proved sufficiency coups and necessity [2] . In 1997, Kheidari and Sudborog showed the lower bound in . They provided accurate values down to for which 15 coups are required [3] . Significantly (up to ) it was only in 2008 that a group of researchers from of managed to surpass the result of Gates and Papadimitriou under the supervision of Sudborog [4] [5] .
The Burned Pancake Problem
A complicated version is a pancake sorting of a sequence whose elements contain an additional binary parameter. This task was proposed by Bill Gates and Christ Papadimitriou in 1979 [2] . It became known as the “ burnt pancake problem ” ( English burnt pancake problem ):
Each pancake in the pile burned on one side. It is required to sort pancakes by increasing (decreasing) diameter so that they all lie on the plate with the burnt side down.
In 2007, a group of students created a biocomputer based on genetically modified E. coli ( E. coli ), which solved the problem of burnt pancakes. The role of pancakes was played by deoxyribonucleic acid fragments (the 3 ′ and 5 ′ ends of which denoted different sides of the pancake). The bacterium, having built the fragments in the necessary order, acquired antibiotic resistance and did not die. The time taken to find the right combination showed the minimum required number of fragment flips [6] [7] .
Implementation
public static void PancakeSort < T > ( IList < T > arr , int cutoffValue = 2 )
where T : IComparable
{
for ( int i = arr . Count - 1 ; i > = 0 ; - i )
{
int pos = i ;
// Find position of max number between beginning and i
for ( int j = 0 ; j < i ; j ++)
{
if ( arr [ j ]. CompareTo ( arr [ pos ]) > 0 )
{
pos = j ;
}
}
// is it in the correct position already?
if ( pos == i )
{
continue ;
}
// is it at the beginning of the array? If not flip array section so it is
if ( pos ! = 0 )
{
Flip ( arr , pos + 1 );
}
// Flip array section to get max number to correct position
Flip ( arr , i + 1 );
}
}
private static void Flip < T > ( IList < T > arr , int n )
where T : IComparable
{
for ( int i = 0 ; i < n ; i ++)
{
- n ;
T tmp = arr [ i ];
arr [ i ] = arr [ n ];
arr [ n ] = tmp ;
}
}
Notes
- ↑ Douglas B. West. The Pancake Problems (1975, 1979, 1973 ) . Date of treatment August 16, 2009. Archived April 5, 2012.
- ↑ 1 2 William H. Gates; Christos H. Papadimitriou. Bounds for sorting by prefix reversal (Eng.) // Discrete Mathematics. - 1979. - Iss. 27 . - P. 47-57 .
- ↑ Mohammad H. Heydari; I. Hal Sudborough. On the diameter of the pancake network (Eng.) // Journal of Algorithms. - Duluth : Academic Press, Inc, 1997. - Vol. 25 , iss. 1 . - P. 67-94 .
- ↑ Team Bests Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics (09/17/2008). Date of treatment August 16, 2009. Archived April 5, 2012.
- ↑ B. Chitturi, W. Fahle, Z. Meng, L. Morales, CO Shields, IH Sudborough, W. Voit. An (18/11) n upper bound for sorting by prefix reversals (Eng.) // Theoretical Computer Science. - Essex : Elsevier Science Publishers Ltd., 2009. - Vol. 410 , iss. 36 . - P. 3372–3390 .
- ↑ Karmella A. Haynes, Marian L. Broderick, Adam D. Brown et al. Engineering bacteria to solve the Burnt Pancake Problem (English) // Journal of Biological Engineering. - 2008 .-- Vol. 2 , iss. 8 .
- ↑ An animated video explaining the solution to a problem by a biological computer (English) . Date of treatment August 16, 2009. Archived April 5, 2012.
See also
- Tower of hanoi
Links
- Weisstein, Eric W. Pancake Sorting . MathWorld. Date of treatment August 16, 2009.
- Alexander Bogomolny. Flipping pancakes . Date of treatment August 16, 2009. Archived April 5, 2012.