BPC-ALD - Skripta_rev2019_2

3  7  5  15  12  1  11  8  17  4  19  10  2  6  9  14 

Bez  vnitřního  třídění  máme  16  vstupních  běhů  po  jednom  prvku.  Tedy  zvolíme  celkový 
počáteční počet běhů 17 a rozdělíme je do tří souborů následovně: 

1. soubor:   3  |  7  |  5  |  15  |  12  |  1  |  11 

2. soubor:   8  |  17  |  4  |  19  |  10  |  2 

3. soubor:   6  |  9  |  14  |  fiktivní 

4. soubor:   -- 

Po prvním průchodu zatřiďování 

1. soubor:   12  |  1  |  11 

2. soubor:   10  |  2 

3. soubor:   -- 

4. soubor:   3  6  8  |  7  9  17  |  4  5  14  |  15  19 

Po druhém průchodu zatřiďování 

1. soubor:   11 

2. soubor:   -- 

3. soubor:   3  6  8  10  12  |  1  2  7  9  17  

4. soubor:   4  5  14  |  15  19 

Po třetím průchodu zatřiďování 

1. soubor:   -- 

2. soubor:   3  4  5  6  8  10  11  12  14   

3. soubor:   1  2  7  9  17  

4. soubor:   15  19 

Ve všech třech souborech, které budou v následujícím průchodu zatřiďování vstupní, je už jen 
jeden běh, čímž tento průchod bude poslední a na jeho konci bude v prvním souboru setříděná 
posloupnost. 

Popsaná  metoda  rozdělování  běhů  se  nazývá  polyfázové  třídění.  Spolu  s použitím  vnitřního 
třídění  pro  vytváření  počátečních  běhů  je  běžně  používána  v třídících  programech  pro  vnější 
třídění. 

− 56 − 

Kontrolní otázky  

1.  Jakým způsobem vytváříme z více vstupních běhů jeden výstupní běh? 
2.  Co je principem polyfázového třídění? 
3.  Jaká je časová složitost vnějšího třídění?