BPC-ALD - Skripta_rev2019_2

Nejpoužívanější 
metodou je 
Quicksort. 

− 50 − 

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

Studijní cíle:  Tato část vysvětluje princip vnějšího třídění a poskytuje podrobný popis metody 
tak, aby ji studující byl schopen případně implementovat. 

Klíčová slova: Běh, zatřiďování, polyfázové třídění. 

Potřebný čas: 1 hodina 30 minut 

Na  rozdíl  od  vnitřního  třídění,  kdy  všechny  tříděné  prvky  jsou  ve  vnitřní  paměti,  při  vnějším 
třídění  jsou  tříděné  prvky  uloženy  v souborech  na  vnějších  pamětích  (pevném  disku).  Třídění 
probíhá tak, že tříděné prvky jsou ze souborů po malých počtech přenášeny do vnitřní paměti, 
v ní jsou zatřiďovány a pak opět ukládány do souborů. Protože operace čtení ze souborů a zápis 
do souborů jsou výrazně pomalejší, než když přesuny prvků probíhají výlučně ve vnitřní paměti, 
je vnější třídění obecně pomalejší než vnitřní třídění a použijeme ho jen v případě, kdy vnitřní 
třídění nelze použít, protože tříděných prvků je tak mnoho, že se všechny do paměti nevejdou. 

3.4.1  Třídění se stejným počtem vstupních a výstupních souborů 

Třídění se stejným počtem vstupních a výstupních souborů je v podstatě nejjednodušší varianta 
vnějšího třídění. Označme si celkový počet souborů použitých při třídění r. Protože vstupních i 
výstupních souborů je stejný počet, musí to být sudé číslo. Minimální počet vstupních souborů, 
aby mohla probíhat operace zatřiďování, je 2, čímž celkový nejmenší možný počet souborů je 4. 
Pro jednodušší zápis si zaveďme i samostatné označení pro počet vstupní souborů, označme si 

ho v (