BPC-ALD - Skripta_rev2019_2

1

2

1

,

,...,

,

h

h

h

h

q

q

−

která je klesající a poslední její hodnota je 1: 

Shellovo třídění 
je založeno na 
třídění přímým 
vkládáním. 

Rozdělením 
tříděné 
posloupnosti na 
více dílčích 
posloupností se 
dosáhne nižší 
složitosti. 

− 32 − 

1

...

1

1

2

1

=

>

>

>

>

−

h

h

h

h

h

q

q

První z hodnot h je největší. Třídění pro ni proběhne rychle, ale přiblížení k cílové pozici bude 
hrubé. Druhá hodnota h už je menší. Zde už bude méně podposloupností a bude tedy každá už 
obsahovat více prvků. 

Připomeňme, že při třídění přímým vkládáním se pozice vložení v setříděné části hledá tak, že 
setříděnou  část  procházíme  odzadu.  U  prvního  průchodu  je  hodnota  h  velká,  čímž 
podposloupnosti  jsou  krátké  a  nalezení  pozic  vložení  probíhá  rychle.  U  dalších  průchodů  se 
délka  podposloupnosti  sice  postupně  zvyšuje,  ale  díky  tomu,  že  bylo  předtím  vždy 
v předchozím  průchodu  provedeno  určité  přiblížení  k cílové  pozici,  budou  pozice  vložení 
většinou poměrně blízko ke konci setříděné části, což znamená nižší počet srovnání a přesunů 
při  vkládání  do  setříděné  části.  Tak  se  to  opakuje  až  po  poslední  hodnotu  h.  Ta  je  ale  1,  což 
znamená, že posledním průchodem je klasické třídění přímým vkládáním, jehož výsledkem je 
vždy setříděná posloupnost bez ohledu na to, jak blízko se prvky v předchozích krocích dostaly 
ke své cílové pozici. Tedy volba posloupnosti hodnot h má vliv jen na účinnost metody, nikoliv 
na výsledek třídění.