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.
0 1 3 4 5 7 8 9 .
Její střední prvek je x = a3 = 4 .
Budou-li na začátku indexy i = 0, j = 7, proběhnou zleva 4 srovnání, než index i skončí na
hodnotě i=3, neboť a3≥x. Zprava proběhne 5 srovnání, než index j skončí na hodnotě j=3, neboť
a3≤x. Tedy celkový počet srovnání je 9, což je o 1 více než je počet prvků v procházené části,
neboť v ní je 8 prvků.
Maximální celkový počet srovnání
=
−
+
+
+
+
+
+
=
+
+
+
+
=
3
1
2
3
...
)
1
(
3
...
)
1
(
n
n
n
n
3
2
)
2
(
)
1
(
−
+
+
=
n
n
Pro počet výměn nám stačí skutečnost, že jich je nejvýše tolik, kolik je srovnání. Celkově je
z toho vidět, že složitost operace srovnání a tím i celé metody je v tomto nejhorším případě
kvadratická.
Naopak optimální případ nastane, když procházená část se vždy rozdělí na dvě stejné části (při
lichém počtu prvků na dvě části lišící se o jeden prvek). Možnost, že dělení také může být na
dvě části a střední prvek, pro jednoduchost opomineme. Spočítáme, kolik nyní bude zapotřebí
třídících průchodů. Sestavíme pro ně následující tabulku
Třídící průchod
Délka částí
1
n
2
2
n
3
2
2
n
….
h
1
2 −
h
n
− 39 −
Každá vytvořená část vstupuje do dalšího třídění, má-li ještě aspoň dva prvky. Pro poslední
třídící průchod z toho dostáváme vztah
2
2 1
=
−
h
n
odtud
n
h
=
2
a dále
)
(
log
2 n
h
=
Tedy počet třídících chodů logaritmicky závisí na počtu tříděných prvků. Zbývá stanovit
složitost operace srovnání v jednom třídícím průchodu. Ta je závislá na tom, na kolik částí je