BPC-ALD - Skripta_rev2019_2

tříděné  pole  rozděleno.  Máme-li  v daném  třídícím  chodu  k  částí,  pak  v každé  z nich  bude 

k

n

prvků. Počet srovnání v každé části je nejvýše o 1 větší než je počet prvků v ní, odtud 

Počet srovnání v jednom třídícím průchodu 

⎟

⎠

⎞

⎜

⎝

⎛ +

×

=

1

k

n

k

. 

V prvním třídícím průchodu chodu je počet částí 1, v posledním, kdy části mají délku 2, je počet 

2

n

.  Dosazením  zjistíme,  že  počet  srovnání  v jednom  třídím  průchodu  se  pohybuje  od  n+1 

v prvním  třídícím  průchodu  až  po 

2

3 n

  v posledním  průchodu.  Tedy  ve  všech  průchodech  je 

složitost  lineární.  Když  vynásobíme  složitost  jednoho  průchodu  počtem  průchodů,  dostaneme 
celkovou složitost: 

))

log(

(

n

n

O

×

 . 

Nyní  je  otázka,  jak  tomu  bude  v běžném  případě.  Ukazuje  se,  že  míra  složitosti  v běžném 
případě je stejná jako v optimálním. Pesimistická kvadratická složitost nejhoršího případu se u 
běžných dat prakticky nevyskytuje. 

Závěr: Složitost metody je typicky

))

log(

(

n

n

O

×

. 

Popsaná metoda je známa zejména pod svým původním anglickým názvem Quicksort (rychlé 
třídění). 

Průvodce studiem  

Algoritmus pro Quicksort vznikl v roce 1962. Tři roky po vzniku Shellova třídění, které 

pochází z roku 1959. 

1.  Proč  jako  referenční  prvek  volíme  prostřední  prvek  v poli,  ačkoliv  optimální  by  bylo 

zvolit prvek, jehož hodnota je uprostřed hodnot všech prvků? 

2.  Jaké  mohou  nastat  případy  rozdělení  pole  na  dvě  části,  v popisu  označené  A  a  B,  tj.