12-Trideni_vnejsi

• Postup zatřiďování: 

1. Do každé z proměnných načteme první prvek z příslušného vstupního běhu. 

• Do 𝑥1čteme prvky z prvního souboru, do 𝑥𝑣 čteme prvky z 𝑣-tého vstupního souboru.  

2. Vybereme nejmenší z prvků 𝑥1, 𝑥2, … , 𝑥𝑣. Nechť tento prvek je 𝑥𝑖. 
3. Prvek 𝑥𝑖 zapíšeme do výstupního souboru, do kterého je ukládán výstupní 

běh. 

4. Do proměnné 𝑥𝑖 načteme z 𝑖-tého vstupního souboru další prvek (pokud v 

příslušném běhu nějaký prvek ještě zbývá). 

5. Body 2 až 4 opakujeme tak dlouho, dokud nejsou všechny prvky z 

proměnných zapsány do výstupního běhu a dokud všechny prvky ze 
současných 𝑣 vstupních běhů nejsou přečteny. 

Třídění se stejným počtem vstupních a 
výstupních souborů – složitost algoritmu 
• Počet operací zatřiďování pro jeden prvek: 

• 1 operace čtení prvku ze souboru do příslušné proměnné. 
•

𝑣 − 1 operací srovnání při hledání nejmenšího prvku v proměnných 

• Operací může být méně, když už jsou některé vstupní běhy vyčerpány. 

• 1 operace zápisu prvku do výstupního běhu. 

• Máme 𝑛 vstupních prvků. Pro jeden průchod zatřiďování provedeme 

𝑛 operací čtení, přibližně 𝑛 ∙ 𝑣 − 1  operací srovnání a 𝑛 operací  
zápisu. (Tedy: 𝑛 + 𝑛 ∙ 𝑣 − 1 + 𝑛.) 

• Protože zvolená konstanta 𝑣 je vzhledem k počtu prvků 𝑛 velmi malá, 

je složitost průchodu zatřiďování lineární. 

Třídění se stejným počtem vstupních a 
výstupních souborů – složitost algoritmu 
• Počet průchodů zatřiďování: 

• V prvním průchodu zatřiďování je délka vstupních běhů 1 prvek. Na výstupu 

vzniknou běhy délky 𝑣. 

• Ve druhém průchodu zatřiďování je délka vstupních běhů 𝑣 a na výstupu 

vznikne výstupní běh délky 𝑣 ∙ 𝑣, atd... 

Třídění se stejným počtem vstupních a 
výstupních souborů – složitost algoritmu