12-Trideni_vnejsi

BPC-ALD 

12. přednáška 

Vnější třídění se stejným počtem vstupních a výstupních souborů, 

odvození složitost algoritmu. Vnější třídění s využitím vnitřního třídění, 

odvození složitosti. 

rev. 2019.2 

Ing. T. Macho, Ph.D. (macho@feec.vutbr.cz) 

Vnější třídění 

Vnější třídění 

• Během třídění jsou tříděné prvky uloženy v souborech ve vnější 

paměti (disku). 

• Tříděné prvky jsou po malých skupinách přeneseny do operační 

paměti, v ní jsou zatřiďovány a pak opět ukládány do souborů.  

• Operace čtení a zápis ze resp. do souboru jsou ve srovnání s 

operacemi přesunu prvků v operační paměti výrazně pomalejší. 

• Vnější třídění je proto pomalejší než vnitřní třídění. 
• Používáme ho pouze tehdy, když třídíme tak velké množství prvků, že 

je nelze všechny současně umístit do operační paměti. 

Třídění se stejným počtem vstupních a 
výstupních souborů 
• Máme 𝑣 vstupních souborů a stejný počet výstupních souborů. 
• Vstupní soubory obsahují setříděné posloupnosti - tzv. běhy. 
• Délka běhu je v prvním kroku 1 prvek, ve druhém kroku 𝑣 prvků, ve 

třetím kroku 𝑣2prvků atd. 

• Vnější třídění je založeno na operaci zatřiďování. 

• Z více setříděných sekvencí je vždy vytvořena jedna delší setříděná sekvence. 

• Algoritmus probíhá ve dvou fázích: 

1. Rozdělování 
2. Zatřiďování 

Třídění se stejným počtem vstupních a 
výstupních souborů 
• Fáze rozdělování 

• Tříděné prvky budeme rovnoměrně rozdělovat do 𝑣 výstupních souborů. 

Třídění se stejným počtem vstupních a 
výstupních souborů - fáze rozdělování 
• Otevřeme 𝑣 souborů pro zápis. 
• První prvek uložíme do prvního souboru, druhý prvek do druhého 

souboru, ... 𝑣-tý prvek do 𝑣-tého souboru. Následující prvek opět do 
prvního souboru atd.