12-Trideni_vnejsi

Průchod 

Délka vstupních běhů 

Délka výstupních běhů 

1 

1 

𝑣 

2 

𝑣 

𝑣2 

3 

𝑣2 

𝑣3 

… 

… 

… 

𝑘 

𝑣𝑘−1 

𝑣𝑘 

Třídění se stejným počtem vstupních a 
výstupních souborů – složitost algoritmu 
• Třídění končí, když výstupní běh obsahuje všech 𝑛 tříděných prvků. 
• Pořadí posledního průchodu proto platí: 𝑣𝑘 = 𝑛. 
• Odtud 𝑘 = 𝑙𝑜𝑔𝑣 𝑛 . 
• Počet průchodů logaritmicky závisí na počtu tříděných prvků. 
• Vynásobíme-li logaritmickou závislost počtu průchodů lineární 

složitostí jednoho průchodu, dostáváme, že složitost metody je: 
 n ∙ 𝑙𝑜𝑔𝑣 𝑛 . 

• Pro třídění je to nejmenší možná složitost, tedy optimální složitost. 

Vnější třídění s využitím vnitřního třídění 

• První běhy u metody třídění se stejným počtem vstupních a 

výstupních souborů, vzniklé ve fázi rozdělování, byly pouze délky 1. 

• Pokud by byly první běhy delší, pak bylo potřeba méně průchodů 

zatřiďování a celkový čas třídění by se zkrátil. 

• Stanovíme počet prvků 𝑚, které se vejdou do paměti. 
• Ve fázi rozdělování načteme 𝑚 prvků do paměti, setřídíme je 

některou z efektivních metod vnitřního třídění (Quick Sort, Heap Sort) 
a setříděnou posloupnost 𝑚 prvků uložíme do příslušného výstupního 
souboru jako jeden běh. 

Vnější třídění s využitím vnitřního třídění 

• Pak pro počty běhů v následujících průchodech zatřiďování bude 

platit: 

Průchod 

Délka vstupních běhů 

Délka výstupních běhů 

1 

𝑚 

𝑚 ∙ 𝑣 

2 

𝑚 ∙ 𝑣 

𝑚 ∙ 𝑣2 

3 

𝑚 ∙ 𝑣2 

𝑚 ∙ 𝑣3 

… 

… 

… 

𝑘 

𝑚 ∙ 𝑣𝑘−1 

𝑚 ∙ 𝑣𝑘 

Vnější třídění s využitím vnitřního třídění