Toto je stará verze stránky VnějšíTřídění z 2007-03-18 21:49:24..

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(?)
polyfázové třídění (něco s Fibonaccim, ale jsem nedával moc pozor)

Poznámky

Nehodí se pro vnitřní třídění. Potřebuje dvojnásobek paměti než Heap Sort (stejná složitost).

*Složitost:* O(logN N)