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.
Příklad. Vezměme posloupnost
7 1 9 5 4 8 3 2
Posloupnost hodnot h zvolme
1
,
2
,
4
1
2
3
=
=
=
h
h
h
Začínáme první hodnotou
4
3 =
h
.
Vyznačme tučně první podposloupnost
7 1 9 5 4 8 3 2
A po jejím setřídění
4 1 9 5 7 8 3 2
Druhá podposloupnost před a po setřídění
4 1 9 5 7 8 3 2
4 1 9 5 7 8 3 2
Třetí podposloupnost před a po setřídění
4 1 9 5 7 8 3 2
4 1 3 5 7 8 9 2
A čtvrtá
4 1 3 5 7 8 9 2
4 1 3 2 7 8 9 5
Nyní vezmeme další hodnotu
2
2 =
h
.
První podposloupnost před a po setřídění
4 1 3 2 7 8 9 5
3 1 4 2 7 8 9 5
Druhá podposloupnost před a po setřídění
3 1 4 2 7 8 9 5
3 1 4 2 7 5 9 8
− 33 −
Na závěr proběhne běžné třídění přímým vkládáním.
Účinnost metody závisí na volbě posloupnosti hodnot
1
2
1
,
,...,
,
h
h
h
h
q
q
−
.
Bude-li hodnot málo, budou skoky mezi nimi dosti velké a předchozí přiblížení bude relativně
hrubé, čímž metoda bude méně efektivní. Bude-li jich naopak hodně, provede se zbytečně
mnoho průchodů, čímž opět poklesne efektivita. Bylo zjištěno, že optimální posloupnost se
vytvoří předpisem