BPC-ALD - Skripta_rev2019_2

3

−

= n

Největší složitost má u této třídící metody operace výběru a ta určuje celkovou složitost metody. 

Závěr: Třídění přímým výběrem má časovou složitost 

Θ(n2). 

Kontrolní otázky  

1.  Jakým způsobem probíhá u metody přímého vkládání nalezení místa, kam má být vložen 

další nesetříděný prvek? 

2.  Jak  by  musela  výchozí  posloupnost  vypadat  (být  uspořádána),  aby  při  bublinkovém 

třídění po každém srovnání musela být provedena výměna? 

3.  Jakým způsobem je u metody přímého výběru realizováno umístění dalšího vybraného 

prvku na svoji cílovou (setříděnou) pozici? 

4.  U  všech  přímých  metod  je  tříděné  pole  rozdělené  na  dvě  části  –  již  setříděnou  a 

doposud  nesetříděnou.  Co  kdybychom  třídili  v opačném  pořadí  (od  největšího  prvku 
k nejmenšímu). Mělo by to vliv na vzájemnou pozici setříděné a nesetříděné části? 

I tato metoda 
má 
kvadratickou 
časovou 
složitost. 

− 30 − 

Cvičení   

1.  Po jednotlivých krocích setřiďte podle abecedy následujících pět písmen metodou 

třídění přímým vkládáním. 

2.  Stejnou posloupnost jako v předchozím cvičení setřiďte bublinkovým třídění. 
3.  Stejnou posloupnost jako v první cvičení setřiďte metodou třídění přímým výběrem. 

Úkoly k textu  

Z popisu bublinkového třídění je zřejmé, že tato třídící metoda se snadno implementuje. Zkuste 
si ji napsat v nějakém programovacím jazyce.  

Řešení  

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

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

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

Průvodce studiem  

V naší zemi žije přibližně 10 miliónů obyvatel. Zkuste si spočítat, jak dlouho by