BPC-ALD - Skripta_rev2019_2

Polyfázové třídění 
promyšleným 
způsobem využívá 
celkový počet 
souborů. 

souborech

− 55 − 

Vezměme  například  stav  na  začátku  průchodu  k-2.  V tomto  okamžiku  v 1.  souboru  zbývají  4 
nepřečtené  běhy,  2.  soubor  je  v této  chvíli  zcela  přečten,  stane  se  tudíž  v tomto  průchodu 
výstupní, v 3. souboru zbývají 2 běhy k přečtení a ve 4. souboru jsou ještě 3 nepřečtené běhy. 
Což  znamená,  že  nejvíce  nepřečtených  běhů  je  v 1.  souboru,  ten  tedy  byl  vytvořen 
v předchozím  třídícím  průchodu  k-3.  Každý  z  běhů  ve  vytvořeném  1.  souboru  byl  vytvořen 
zatříděním  běhů  ze  zbývajících  tří  souborů.  Pro  4  vytvořené  běhy  byly  tedy  z každého  ze 
vstupních souborů přečteny 4 běhy. Tedy každý z těchto souborů na začátku průchodu k-2 měl o 
4 nepřečtené běhy více než na jeho konci. 2. soubor na konci tohoto průchodu už nemá žádný 
nepřečtený  běh,  tedy  předtím  měl  4  nepřečtené,  3.  soubor  má  na  konci  2  nepřečtené,  tudíž 
předtím musel mít 6 nepřečtených běhů atd. 

Ve fázi rozdělování je nutné tyto počty dodržet. Jestliže například vnitřním tříděním získáme 50 
běhů, pak zvolíme k tomu nejbližší možný celkový počet běhů, což je 57. Do prvního souboru 
dáme 24 běhů, do druhého 20 běhů, do třetího zbývajících 6 běhů, které do požadovaného počtu 
13 běhů doplníme 7 fiktivními běhy, což jsou běhy nulové délky (neobsahující žádný prvek). 

Příklad. Budeme opět třídit prvky