BPC-ALD - Skripta_rev2019_2

− 49 − 

3.3.4  Srovnání metod vnitřního třídění 

Probrali jsme celkem 6 metod vnitřního třídění. První 3 byly přímé, jednodušší metody. Jejich 
složitost  byla  u  všech  stejná 

Θ(n2).  Protože  je  to  citelně  vyšší  složitost  než  u  dokonalejších 

metod, použijeme je jen v případech, kdy počet tříděných prvků není tak velký. Z odhadů, který 
jsme učinili v první kapitole o složitosti, že dá říci, že přímé metody vyhovují do řádově tisíce 
tříděných prvků. Implementačně nejjednodušší z nich je bublinkové třídění. Celý program pro 
tuto  metody  se  skládá  ze  dvou  vnořených  cyklů.  Nejrychlejší  z nich  je  třídění  přímým 
vkládáním. Plyne to ze skutečnosti, že tato metoda ve srovnání se zbývajícími dvěma metodami 
má méně operací srovnání, což má vliv na čas tříděný. 

Ze zbývajících  tří  metod  má  nejhorší  složitost  Shellovo  třídění  (

Θ(n1.2)).  Věcně  není  žádný 

důvod,  proč  bychom  ho  měli  zvolit,  neboť  máme  další  dvě  metody,  jež  mají  lepší  složitost. 
Metoda  Quicksort  má  očekávanou  složitost 

Θ(n∗log(n))  a  třídění  haldou  ji  má  dokonce 

zaručenou.  Dá  se  i  dokázat,  že  nelze  sestavit  třídící  metodu,  která  by  měla  lepší  složitost  než 

Θ(n∗log(n)). Lepší složitost mají jen určité specifické metody jako je adresní třídění, které jsou 
ale použitelné jen ve značně speciálních případech. Kdybychom si nyní měli vybrat podle toho, 
jak  obtížná  je  jejich  implementace,  je  zřejmé,  že  bychom  zvolili  metodu  Quicksort.  Ta  se 
naprogramuje  poměrně  snadno.  Je  to  jedna  rekurzivní  procedura  se  dvěma  formálními 
parametry  –  počátečním  a  koncovým  indexem  tříděné  části  pole.  V praxi  se  také  tato  metoda 
nejčastěji používá. Přitom je nejen implementačně jednodušší, ale běžně má i nižší čas třídění 
než  má  třídění  haldou.  Příčina,  proč  třídění  haldou  trvá  déle,  tkví  v jeho  poměrně 
komplikovaném algoritmu.