BPC-ALD - Skripta_rev2019_2
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
doposud popsanými algoritmy trvalo setřídění jejich jmen podle abecedy, kdybychom
− 31 −
srovnání dvou jmen udělali vždy za 1 mikrosekundu.Určitě zjistíte, že je zapotřebí se
zabývat i výkonnějšími algoritmy.
3.3 Účinnější metody vnitřního třídění
3.3.1 Shellovo třídění
Studijní cíle: Tato část vysvětluje princip Shellova třídění a poskytuje podrobný popis
algoritmu tak, aby ho studující byl schopen případně implementovat.
Klíčová slova: Shellovo třídění.
Potřebný čas: 1 hodina
Shellovo třídění je třídění vkládáním. Vychází z již probrané metody třídění přímým vkládáním.
Připomeňme, že průměrná složitost operací této metody je přibližně (po zanedbání lineárního a
konstantního členu)
4
2
n
.
Aplikujme nyní třídění přímým vkládáním ne na celou posloupnost s n prvky, ale na h jejích
podposloupností, kde h>1. Tyto podposloupnosti sestavíme tak, že budeme postupně vybírat
prvky, jež jsou od sebe vzdáleny o h prvků:
1. podposloupnost:
,...
,
,
1
2
1
1
+
∗
+
h
h
a
a
a
2. podposloupnost:
,...
,
,
2
2
2
2
+
∗
+
h
h
a
a
a
….
h-tá podposloupnost:
,...
,
,
3
2
h
h
h
a
a
a
∗
∗
Každá z těchto podposloupností místo n prvků má řádově jen
h
n
prvků. Složitost operací je u
každé z těchto podposloupností
2
2
2
4
4
h
n
h
n
=
⎟
⎠
⎞
⎜
⎝
⎛
.
Podposloupností je h, složitost operací pro všech h podposloupností bude
h
n
h
n
h
4
4
2
2
2
=
×
To je viditelně méně, než když se přímé třídění provádí jen na jedné posloupnosti se všemi
prvky najednou. Tříděním samostatných podposloupností se přirozeně nedosáhne setřídění celé
posloupnosti. Prvky tak vesměs nebudou na své cílové pozici. Ale dostanou se tímto do určité
blízkosti ke své cílové pozici. Jak blízko budou, bude záviset na hodnotě h. Čím bude h menší,
tím blíže budou u své cílové pozice. Na druhé straně ale, čím h bude větší, tím příznivější bude
složitost třídění všech podposloupností. Tento rozpor Shellovo třídění řeší tak, že dělení na více
podposloupností nedělá jen jednou, ale vícekrát, přičemž postupně přitom snižuje velikost
hodnoty h. Shellovo třídění tedy vychází z určité stanovené posloupnosti hodnot h