BPC-ALD - Skripta_rev2019_2

3.4.3  Polyfázové třídění 

Vraťme se ke vztahu, jež udává počet průchodů zatřiďování: 

Složitost vnějšího 
třídění je 
optimální.

Vnější třídění lze 
zefektivnit 
využitím 
vnitřního třídění. 

− 54 − 

)

(

log

)

(

log

m

n

k

v

v

−

=

 . 

Je zřejmé, že počet potřebných průchodů zatřiďování mimo jiné závisí na základu logaritmu v, 
tj. počtu vstupních souborů. Čím větší tento bude, tím méně průchodů bude potřeba. Můžeme 
sice počet vstupních souborů zvýšit zvolením větší počtu celkově používaných souborů, ale na 
druhé straně příliš mnoho používaných souborů má negativní vliv na výkonnost systému. Spíše 
se nabízí myšlenka celkový počet r používaných souborů využít efektivněji a to tak, že místo 
rozdělení 

2

r

 vstupních souborů  +  

2

r

 výstupních souborů 

použít rozdělení 

1

−

r

 vstupních souborů  +  1 výstupní soubor . 

Při tomto rozdělení musí mít vstupní soubory rozdílné počty běhů, aby jeden z nich se vyčerpal 
dříve než ostatní. V tom okamžiku se vyčerpaný vstupní soubor uzavře a stane se nyní novým 
výstupním  souborem  a  dosavadní  výstupní  soubor  se  rovněž  uzavře  a  přidá  se  ke  vstupním 
souborům.  Aby  tento  princip  fungoval  po  celou  dobu  třídění,  musí  ve  fázi  rozdělování  být 
vstupní běhy rozděleny do r-1 vytvářených souborů ve specifických počtech. 

Vezměme například celkový počet souborů r=4. Při odvození, kolik běhů musí být na začátku 
ve  fázi  rozdělování  uloženo  do  jednotlivých  souborů,  vyjdeme  ze  situace,  která  je  na  konci 
třídění – 3 současně vyčerpané vstupní soubory a 1 běh na výstupním souboru. Což znamená, že 
než začalo ukládání běhů na výstupní soubor, musel na všech 3 vstupních soubor v této chvíli 
zbývat právě jeden běh. Když budeme touto úvahou pokračovat dál dostaneme: