Pannkaka sort

Pancake sortering (från engelska  pancake sorting ) - sorteringsalgoritm . Den enda operation som tillåts i algoritmen är att vända elementen i sekvensen upp till något index. Till skillnad från traditionella algoritmer som minimerar antalet jämförelser, kräver pannkakssortering så få vändningar som möjligt. Processen kan visualiseras som en bunt pannkakor , som blandas genom att ta flera pannkakor uppifrån och vända dem.

Algoritm

Den enklaste algoritmen ( selekteringssorteringsvariant ) ger inga fler vändningar, utan kräver att man hittar det största elementet [1] . 1979 presenterade Bill Gates och Christos Papadimitriou sin algoritm och bevisade tillräckligheten och nödvändigheten av vändningar [2] . 1997 visade Heidari och Sudborog den nedre gränsen i . De gav exakta värden upp till , vilket kräver 15 vändningar [3] . Det var först 2008 som en grupp forskare från University of Texas i Dallas ledd av Sudborog [4] [5] lyckades avsevärt (upp till ) överträffa resultatet av Gates och Papadimitriou .

Problem med bränd pannkaka

En mer komplicerad version är en pannkaka av en sekvens vars element innehåller en extra binär parameter. Detta problem föreslogs av Bill Gates och Christos Papadimitriou 1979 [2] . Det blev känt som problemet med brända pannkakor : 

Varje pannkaka i högen brändes på ena sidan. Det krävs att pannkakorna sorteras i stigande (fallande) diameter så att de alla ligger på tallriken med den brända sidan nedåt.

2007 skapade en grupp studenter en biodator baserad på genetiskt modifierad E. coli som löste problemet med bränd pannkaka . Pannkakors roll spelades av fragment av deoxiribonukleinsyra (vars 3'- och 5'-ändar betecknade olika sidor av pannkakan). Bakterien, efter att ha byggt fragmenten i rätt ordning, fick resistens mot antibiotikan och dog inte. Tiden som gick åt för att söka efter den korrekta kombinationen visade det minsta antal fragment som krävs [6] [7] .

Implementering

C# public static void PancakeSort < T >( IList < T > arr , int cutoffValue = 2 ) där T : IComparable { for ( int i = arr . Count - 1 ; i >= 0 ; - i ) { int pos = i ; // Hitta position för maxtal mellan början och i för ( int j = 0 ; j < i ; j ++) { if ( arr [ j ]. CompareTo ( arr [ pos ]) > 0 ) { pos = j ; } } // är den redan i rätt läge? if ( pos == i ) { fortsätt ; } // är det i början av arrayen? Om inte vänd array-sektionen så är det om ( pos != 0 ) { Flip ( arr , pos + 1 ); } // Vänd arraysektionen för att få maxnummer till rätt position Flip ( arr , i + 1 ); } } privat statisk tomrum Vänd < T >( IList < T > arr , int n ) där T : IComparable { for ( int i = 0 ; i < n ; i ++ ) { -- n ; Ttmp = arr [ i ] ; arr [ i ] = arr [ n ]; arr [ n ] = tmp ; } }

Anteckningar

  1. ↑ Douglas B. West. The Pancake Problems (1975, 1979, 1973  ) Hämtad 16 augusti 2009. Arkiverad från originalet 5 april 2012.
  2. ↑ 1 2 William H. Gates; Christos H. Papadimitriou. Gränser för sortering efter prefixomkastning  //  Diskret matematik. - 1979. - Iss. 27 . - S. 47-57 . Arkiverad från originalet den 10 juni 2007.
  3. ↑ Mohammad H. Heydari; I. Hal Sudborough. Om pannkaksnätverkets diameter  (engelska)  // Journal of Algorithms. - Duluth : Academic Press, Inc., 1997. - Vol. 25 , iss. 1 . - S. 67-94 .
  4. ↑ Lagbästa unga Bill Gates med förbättrat svar på så kallade pannkaksproblem i matematik  ( 17 september 2008). Hämtad 16 augusti 2009. Arkiverad från originalet 5 april 2012.
  5. ↑ B. Chitturi, W. Fahle, Z. Meng, L. Morales, CO Shields, I. H. Sudborough, W. Voit. En (18/11)n övre gräns för sortering efter prefixomkastningar  (engelska)  // Teoretisk datavetenskap. - Essex : Elsevier Science Publishers Ltd., 2009. - Vol. 410 , iss. 36 . - P. 3372-3390 .
  6. ↑ Karmella A. Haynes, Marian L. Broderick, Adam D. Brown et al. Ingenjörsbakterier för att lösa problemet med bränd pannkaka  //  Journal of Biological Engineering. - 2008. - Vol. 2 , iss. 8 .
  7. ↑ Animerad video som förklarar lösningen av problemet med en biologisk dator  (engelska) . Hämtad 16 augusti 2009. Arkiverad från originalet 5 april 2012.

Se även

Länkar

  • Weisstein, Eric W. Pannkakssortering  . matematikvärlden. Hämtad: 16 augusti 2009.
  • Alexander Bogomolny. Vänd  pannkakor . Hämtad 16 augusti 2009. Arkiverad från originalet 5 april 2012.
 Sorteringsalgoritmer
Teori Komplexitet O notation Orderförhållande Sorteringstyper hållbar Inre Extern
Utbyta
Val
Insatser
fusion
Inga jämförelser
hybrid
Övrig
opraktisk