Druh palačinky

Pancake sorting (z anglického  pancake sorting ) - třídící algoritmus . Jedinou operací povolenou v algoritmu je obrátit prvky sekvence až k nějakému indexu. Na rozdíl od tradičních algoritmů, které minimalizují počet porovnávání, vyžaduje třídění palačinek co nejméně převrácení. Proces lze zobrazit jako stoh palačinek , který se zamíchá tak, že se vezme několik palačinek shora a převrátí se.

Algoritmus

Nejjednodušší algoritmus ( varianta seřazení výběru ) neposkytuje žádné další převrácení, ale vyžaduje nalezení největšího prvku [1] . V roce 1979 Bill Gates a Christos Papadimitriou představili svůj algoritmus a prokázali dostatečnost a nezbytnost flipů [2] . V roce 1997 Heidari a Sudborog vykazovali spodní hranici v . Poskytovaly přesné hodnoty až , což vyžaduje 15 překlopení [3] . Teprve v roce 2008 se skupině výzkumníků z Texaské univerzity v Dallasu pod vedením Sudboroga [4] [5] podařilo výrazně (až ) překonat výsledek Gatese a Papadimitrioua .

Problém s připálenou palačinkou

Složitější verzí je placka typu sekvence, jejíž prvky obsahují další binární parametr. Tento problém navrhli Bill Gates a Christos Papadimitriou v roce 1979 [2] . Stalo se to známé jako problém spálených palačinek : 

Každá palačinka ve stohu byla spálená na jedné straně. Placky je nutné třídit ve vzestupném (sestupném) průměru tak, aby všechny ležely na plechu připálenou stranou dolů.

V roce 2007 vytvořila skupina studentů biopočítač založený na geneticky modifikované E. coli , který vyřešil problém spálených palačinek . Roli palačinek sehrály úlomky deoxyribonukleové kyseliny (jejíž 3'- a 5'-konce označovaly různé strany palačinky). Bakterie, která vytvořila fragmenty ve správném pořadí, získala odolnost vůči antibiotiku a nezemřela. Čas strávený hledáním správné kombinace ukázal minimální požadovaný počet převrácení fragmentů [6] [7] .

Implementace

C# public static void PancakeSort < T > ( IList < T > arr , int cutoffValue = 2 ) kde T : IComparable { for ( int i = arr . Count - 1 ; i >= 0 ; -- i ) { int pos = i ; // Zjištění pozice max. čísla mezi začátkem a i for ( int j = 0 ; j < i ; j ++) { if ( arr [ j ]. CompareTo ( arr [ pos ]) > 0 ) { pos = j ; } } // je již ve správné poloze? if ( pos == i ) { pokračovat ; } // je na začátku pole? If not flip array section tak to je if ( pos != 0 ) { Flip ( arr , pos + 1 ); } // Překlopte sekci pole pro získání maximálního čísla na správnou pozici Flip ( arr , i + 1 ); } } private static void Flip < T >( IList < T > arr , int n ) kde T : IComparable { for ( int i = 0 ; i < n ; i ++) { -- n ; Ttmp = arr [ i ] ; arr [ i ] = arr [ n ]; arr [ n ] = tmp ; } }

Poznámky

  1. ↑ Douglas B. West. Problémy s palačinkami (1975, 1979, 1973  ) Získáno 16. srpna 2009. Archivováno z originálu dne 5. dubna 2012.
  2. ↑ 1 2 William H. Gates; Christos H. Papadimitriou. Hranice pro řazení podle obrácení předpony  //  Diskrétní matematika. - 1979. - Iss. 27 . - str. 47-57 . Archivováno z originálu 10. června 2007.
  3. ↑ Mohammad H. Heydari; I. Hal Sudborough. O průměru palačinkové sítě  (anglicky)  // Journal of Algorithms. - Duluth : Academic Press, Inc, 1997. - Sv. 25 , iss. 1 . - str. 67-94 .
  4. ↑ Tým zvítězil nad mladým Billem Gatesem s vylepšenou odpovědí na takzvaný palačinkový problém v matematice  ( 17. září 2008). Získáno 16. srpna 2009. Archivováno z originálu dne 5. dubna 2012.
  5. ↑ B. Chitturi, W. Fahle, Z. Meng, L. Morales, CO Shields, I. H. Sudborough, W. Voit. Horní hranice (18/11)n pro třídění podle obrácení předpon  (anglicky)  // Theoretical Computer Science. - Essex : Elsevier Science Publishers Ltd., 2009. - Sv. 410 , iss. 36 . - str. 3372-3390 .
  6. ↑ Karmella A. Haynes, Marian L. Broderick, Adam D. Brown a kol. Inženýrské bakterie k vyřešení problému spálených palačinek  //  Journal of Biological Engineering. - 2008. - Sv. 2 , iss. 8 .
  7. ↑ Animované video vysvětlující řešení problému biologickým počítačem  (anglicky) . Získáno 16. srpna 2009. Archivováno z originálu dne 5. dubna 2012.

Viz také

Odkazy

  • Weisstein, Eric W. Třídění  palačinek . matematický svět. Staženo: 16. srpna 2009.
  • Alexandr Bogomolnyj. Obracející  palačinky . Získáno 16. srpna 2009. Archivováno z originálu dne 5. dubna 2012.
 Algoritmy řazení
Teorie Složitost O zápis Objednávkový vztah Seřadit typy udržitelného Vnitřní Externí
Výměna
Výběr
vložky
fúze
Žádné srovnání
hybridní
jiný
nepraktický