12-Trideni_vnejsi

Třídění se stejným počtem vstupních a 
výstupních souborů - fáze rozdělování, příklad 

• Uvažujme vstupní posloupnost prvků 𝑎1, 𝑎2, 𝑎3, … , 𝑎𝑛, které máme 

setřídit. 

• Rozdělení do 𝑣 výstupních souborů bude následující: 

1. soubor: 𝑎1, 𝑎𝑣+1, … , 𝑎2∗𝑣+1, … 

2. soubor: 𝑎2, 𝑎𝑣+2, … , 𝑎2∗𝑣+2, … 

... 

𝑣-tý soubor: 𝑎𝑣, 𝑎2∗𝑣, 𝑎3∗𝑣, … 

Třídění se stejným počtem vstupních a 
výstupních souborů - fáze zatřiďování 

•

𝑣 souborů, do nichž jsme prvky rozdělili, nyní otevřeme jako vstupní. 

• Ze všech vstupních souborů načteme jejich první běh, zatříděním z 

něho vytvoříme jeden setříděny výstupní běh a ten uložíme do 
prvního výstupního souboru. 

• Pak ze všech vstupních souborů načteme druhý běh, zatříděním z 

něho vytvoříme další setříděný výstupní běh a ten uložíme do 
druhého výstupního souboru. 

• Až 𝑣-tý výstupní běh uložíme do 𝑣-tého výstupního souboru, 𝑣 + 1 

výstupní běh uložíme zase do prvního výstupního souboru atd. 

Třídění se stejným počtem vstupních a 
výstupních souborů - fáze zatřiďování 

• Když jsou všechny běhy ze vstupních souborů přečteny, vstupní i 

výstupní soubory uzavřeme. 

• Soubory, které byly výstupní nyní otevřeme jako vstupní a soubory, 

které byly jako vstupní otevřeme jako nové výstupní. (Vyměníme tedy 
funkci souborů.) 

• Opakujeme proces zatřiďování. 
• Postup probíhá tak dlouho, dokud nezískáme jeden výstupní běh, 

který bude obsahovat všechny setříděné prvky.   

Třídění se stejným počtem vstupních a 
výstupních souborů - algoritmus zatřiďování 

• K zatřiďování potřebujeme tolik proměnných, kolik je vstupních 

souborů, tedy 𝑣. 

• Proměnné označíme: 𝑥1, 𝑥2, … , 𝑥𝑣. 

Třídění se stejným počtem vstupních a 
výstupních souborů - algoritmus zatřiďování