BPC-ALD - Skripta_rev2019_2

A poslední průchod, při kterém vznikne běh délky 16: 

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

2. soubor:   -- 

Zbývá popsat, jak probíhá vlastní zatřiďování v vstupních běhů v jeden výstupní běh.  

Algoritmus zatřiďování 

K zatřiďování potřebujeme tolik proměnný, kolik je vstupních souborů, tedy v. Tyto proměnné 
si označme 

v

x

x

x

,...,

,

2

1

proměnných

− 52 − 

1. Do každé z proměnných

v

x

x

x

,...,

,

2

1

načteme první prvek z v vstupních běhů. 

2. Vybereme nejmenší z prvků v

v

x

x

x

,...,

,

2

1

. Nechť tento prvek je třeba v proměnné xi. Prvek 

zapíšeme do výstupního souboru, do kterého je právě ukládán výstupní běh, a do proměnné xi 

načteme další prvek z i-tého vstupní běhu (zbývá-li v něm ještě nějaký). Tento proces pokračuje 
tak  dlouho,  dokud  všechny  prvky  z proměnných  nejsou  zapsány  do  výstupního  běhu  a  dokud 
všechny prvky ze současných v vstupních běhů nejsou vyčerpány. 

Příklad. Budeme zatřiďovat dva vstupní běhy délky 4 z minulého příkladu 

3  5  7  15 

1  8  11  12 

Po načtení prvních prvků do proměnných je: 

x1 = 3      v 1. běhu zbývá:  5  7  15 
x2 = 1      v 2. běhu zbývá:  8  11  12 

Vybereme  nejmenší  prvek  1  a  zapíšeme  ho  na  výstup.  Na  jeho  místo  načteme  další  prvek 
z příslušného běhu: 

x1 = 3      v 1. běhu zbývá:  5  7  15 
x2 = 8      v 2. běhu zbývá:  11  12 

Vybereme nejmenší prvek 3 a zapíšeme ho na výstup. 

x1 = 5      v 1. běhu zbývá:  7  15 
x2 = 8      v 2. běhu zbývá:  11  12