BPC-ALD - Skripta_rev2019_2

část,i mezi kterými už nebudou žádné výměny? 

3.  Jaká je časová složitost třídění Quicksort? 

Cvičení   

1.  Metodou Quicksort setřiďte podle abecedy následujících sedm písmen. 

2.  Jak bude třídění probíhat pro následující opačně uspořádanou posloupnost pěti písmen: 

Složitost metody 
je typicky 
Θ(n

∗log(n)). 

− 40 − 

Úkoly k textu  

V popis metody jsme uvedli, že při výběru referenčního prvku by bylo optimální vzít prvek, 
jehož hodnota je uprostřed všech hodnot v procházené části pole. Místo toho ale bereme prvek, 
který leží uprostřed. Tedy máme-li posloupnost prvků 
               2  5  8  4  9 
pak prvek uprostřed je 8, což následně vede na rozdělení na části 
               2  5  4  8  -  9  . 
Ale kdybychom vzali prvek s hodnotou uprostřed, což je 5, bylo by rozdělení na části mnohem 
příznivější 
               2  4  5  -  8  9  . 
Jako důvod jsme uvedli. že nalezení prvku s hodnotu uprostřed je značně časově náročné. 
Zkuste se zamyslet, jak by asi vypadal algoritmus pro nalezení prvku s prostřední hdonotou a 
jakou by měl asi časovou složitost. Konkrétně bychom potřebovali, aby měl lineární složitost. 
Neboť pak bychom vzhledem k tomu, že dělení v tomto případě vede na dvě přibližně stejné 
části a tedy na logaritmickou závislost počtu třídících kroků, měli zaručenou celkovou složitost 
rovnu součinu lineární a logaritmické, což je 

Θ(n∗log(n)).  

Řešení  

1.  Postup třídění ukazuje následující obrázek: 

2.  Postup třídění ukazuje následující obrázek: 

− 41 − 

3.3.3  Třídění použitím haldy 

Studijní cíle:  Tato  část  vysvětluje  princip  třídění  haldou  a  poskytuje  podrobný popis  metody 
tak, aby ji studující byl schopen případně implementovat. 

Klíčová slova: Halda, binární strom.