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.
Průměrný počet srovnání
=
−
+
+
+
+
=
+
+
+
=
2
)
1
(
...
3
2
1
2
...
3
2
n
n
4
2
2
1
2
)
1
(
2
−
+
=
−
+
=
n
n
n
n
Maximální počet srovnání
2
2
)
1
(
)
1
(
...
2
1
2
n
n
n
n
n
−
=
−
=
−
+
+
+
=
Při stanovení
složitosti třídění
uvažujeme
operace srovnání
a operace vložení.
(n) - 1
− 25 −
Z toho plyne, že operace srovnání má kvadratickou složitost bez ohledu na to, zda uvažujeme
průměrný nebo maximální počet srovnání.
Nyní uvažujme operaci přesunu prvku o jednu pozici dozadu. Těch v jednom kroku proběhne 0
až k podle toho, na které místo je prvek vkládán . Odtud pro jeden krok dostáváme
Průměrný počet přesunů
2
2
0
k
k
=
+
=
Maximální počet přesunů = k
A pro celé třídění dostaneme
Průměrný počet přesunů
4
2
2
)
1
(
2
)
1
(
...
2
1
2
n
n
n
n
n
−
=
−
=
−
+
+
+
=
Maximální počet přesunů
2
2
)
1
(
)
1
(
...
2
1
2
n
n
n
n
n
−
=
−
=
−
+
+
+
=
Z toho plyne, že operace přesunu má kvadratickou složitost bez ohledu na to, zda uvažujeme
průměrný nebo maximální počet přesunů.
Jestliže algoritmus zahrnuje více operací, výsledná míra složitosti se odvozuje vždy od operace,
která má největší složitost. Zde obě operace mají stejnou míru složitosti - kvadratickou.
Závěr: Třídění přímým vkládáním má časovou složitost
Θ(n2).
3.2.2 Třídění přímou výměnou (bublinkové třídění)
Při třídění přímou výměnou procházíme postupně pole s tříděnými prvky směrem od začátku
k jeho konci a srovnáváme sousední dvojice, zda prvky v nich jsou podle velikosti ve správném
pořadí. Jestliže ne, tedy větší prvek je před menším, provedeme jejich vzájemnou výměnu.
Snadno se ověří, že největší prvek obsažený v tříděné posloupnosti se těmito výměnami dostane
na konec, tedy na své cílové místo, ať byl předtím kdekoliv. V další kroku celý postup
zopakujeme, ale už bez posledního prvku, tedy jen s prvními n-1 prvky. Při něm se obdobným
způsobem dostane na své cílové místo předposlední prvek setříděné posloupnosti.
V následujícím kroku už budeme procházet jen n-2 prvků atd. Je zřejmé, že každým průchodem
se délka procházené části sníží o jeden prvek, až nakonec v posledním průchodu bude
procházená část mít jen dva prvky a po jejich srovnání a případné výměně je třídění dokončeno.