BPC-ALD - Skripta_rev2019_2

1

1

2

,

1

1

1

>

+

×

=

=

−

i

pro

h

h

h

i

i

což znamená posloupnost 

…., 127, 63, 31, 15, 7, 3, 1 

Zbývá otázka, kterou z těchto hodnot zvolit jako první. To závisí na počtu tříděných prvků n. 
Zvolíme  největší  z  těchto  hodnot  takovou,  aby  v každé  z podposloupností  bylo  co  třídit,  tedy 
aby obsahovala aspoň 2 prvky. Odtud pro první zvolenou hodnotu hq dostáváme podmínku 

2

n

h

q ≤

 . 

Budeme-li například třídit 100 prvků, použijeme posloupnost 

31, 15, 7, 3, 1 . 

Odvození časové složitosti Shellova třídění je obtížné. Uveďme proto jen výsledek 

Θ(n1.2). 

Číslům  h  se  také  říká  kroky  Shellova  třídění  a  samotná  metoda  bývá  také  nazývána  tříděním 
vkládáním s ubývajícím krokem. 

Kontrolní otázky  

1.  Kdybychom  v setříděné  části  hledali  místo  pro  vložení  dalšího  prvku  odpředu  místo 

odzadu, mělo by to vliv na účinnost Shellova třídění? 

2.  Proč posloupnost kroků třídění volíme klesající? 
3.  Jaká je časová složitost Shellova třídění? 

Cvičení   

1.  Po jednotlivých krocích Shellovým tříděním setřiďte podle abecedy následujících sedm 

písmen. Zvolte přitom optimální posloupnost kroků. 

2.  Máme setřídit 1000 prvků. Jaká je optimální posloupnost kroků? 

Úkoly k textu  

Zamyslete se nad tím, co kdybychom stejnou myšlenku rozdělení na více dílčích posloupností 
uplatnili u bublinkového třídění. Mělo by to nějaký zásadní vliv na složitost metody?  

Volba dělení na 
dílčí posloupnosti 
je kritická pro 
efektivnost 
metody. 

1.5

(označovaná v literatuře jako Hibbardova posloupnost):

− 34 − 

Řešení  

1.  Protože máme 7 prvků, optimální posloupnost kroků bude mít dva členy h2=3 a h1=1. 

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

2.  Máme-li třídit 1000 prvků, můžeme je rozdělit do nejvýše 500 dílčích posloupností, aby