Vnější třídění
Narozdíl od
vnitřního třídění máme data v souboru (z historických důvodů se říká na pásce, prý), nemáme přímý přístup. Všechny probírané algoritmy využívají slučování/slévaní (angl. merge).
Počítání složitosti
Jako operace se bere čtení a zápis (narozdíl od vnitřního třídění).
Algoritmy
Přímé slučování
(alias
Dvoufázové dvoucestné přímé slučování)
Mějme posloupnost, rozdělme ji na dvě posloupnosti, sestávající ze setříděných posloupností délky 1. Slučme tyto setříděné posloupnosti. Atd. Na celé setřídění je třeba log
N rozdělení a sloučení. Každé sloučení i rozdělení sestává z
N čtení +
N zápisů,
Fígle
- střídavě budeme při zápisů sloučení psát do jednoho a druhého souboru, 2x (konstantní) zrychlení (pak už není dvoufázové)
- vícecestné (k-cestné) třídění – změní se základ logaritmu na k, takže k/2x (konstantní) zrychlení.
- přirozené místo přímé slučování – budeme slučovat běhy (run), maximální uspořádané posloupnosti
Extra fígle
- předtřídíme malé podposloupnosti vnitřním tříděním (tím si vytvoříme běhy), log (co se vejde do paměti) se odečte od složitosti (?)- Je to tak, ze pokud se nam do pameti vejde 1000 prvku tak usetrime log 1000 prvnich kroku trideni “venku” vymenou za – zanedbatelnou – dobu trideni toho 1000 prvku uvnitr (treba Quick Sortem). Mudrc
- polyfázové třídění (něco s Fibonaccim, ale jsem nedával moc pozor)
Poznámky
*Složitost:* O(
N log
N)
http://www.gvid.cz/projekty_sipvz/trideni.ppt