BPC-ALD - Skripta_rev2019_2

Cvičení   

1.  Ukažte, jak proběhne vnějším tříděním bez použití vnitřního třídění a se dvěma 

vstupními a dvěma výstupními soubory pro následující písmena. 

2.  Jak bude probíhat zatřídění tří následujících běhů délky 3: 

3.  Máme setřídit 100000 záznamů. V paměti dokážeme třídit 2000 záznamů. Použijeme 

celkově 5 souborů. Budeme třídit polyfázovým tříděním. Napište, kolik bude na začátku 
na 4-ti vstupních souborech běhů. 

Úkoly k textu  

Při polyfázovém třídění nemají běhy v jednotlivých vstupních souborech stejnou délku. 
Například používáme-li 3 vstupní soubory a počáteční délka běhů je m, pak na začátku je délka 
běhů ve všech souborech stejná 
    m    m    m  . 
Při prvním průchodu z nich vznikají běhy délky 3m. Po vyčerpání prvního souboru a následném 
zařazení výstupního souboru na vstup už délky budou 
    3m    m    m  . 
Zamyslete se nad tím, jak to postupně bude vypadat po vyčerpání dalších vstupních souborů. 

Řešení  

1.  Postup rozdělování a následné zatřiďování ukazuje následující obrázek: 

− 57 − 

2.  Průběh zatřiďování ukazuje následující obrázek: 

3.  Při vnitřním třídění po 2000 prvcích dostaneme pro 100000 vstupních prvků 50 běhů. 

Odvodíme nejmenší počet vstupních běhů pro polyfázové třídění, který je roven 50 
nebo větší než 50. 

K

L

I

I

− 58 − 

Z předchozího obrázku plyne, že musíme zvolit 94 počátečních běhů – 50 získaných 
tříděním + 44 fiktivních. 

− 59 − 

4  Vyhledávání 

Vyhledávání je další velmi důležitou a často se vyskytující úlohou. Při ní máme opět zadanou 
nějakou množinu prvků a cílem je nalézt mezi nimi takový prvek, který má danou hodnotu, 
anebo případně zjistit, že takový prvek mezi nimi není. 
Máme tedy n prvků dat 

n

a

a

a

...

,

,

2

1

  , 

dále  máme  dánu  hodnotu  prvku,  označme  ji    x  (nebo  hodnotu  klíče  prvku,  hledáme-li  mezi 
strukturovanými prvky, tj. záznamy) a hledáme prvek ai, pro který platí