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.
Celkový počet srovnání
2
2
)
1
(
1
...
)
2
(
)
1
(
2
n
n
n
n
n
n
−
=
−
=
+
+
−
+
−
=
Nyní uvažujme operaci výměn. Výměn se provede maximálně tolik, kolik je srovnání.
Minimální možný počet výměn je žádná výměna (prvky jsou na začátku uspořádány tak, že jsou
setříděné). Přitom za základní operaci zde nepovažujeme přímo výměnu, ale operace přesunů,
pomocí kterých je výměna provedena. Jedna výměna vyžaduje tři přesuny:
1. První prvek přesuneme do pracovní proměnné.
Složitost metody
této metody je
kvadratická.
− 27 −
2. Druhý prvek přesuneme na místo prvního prvku.
3. První prvek, který je v současnosti uložený v pracovní proměnné, přesuneme z pracovní
proměnné na místo druhého prvku.
Odtud dostáváme pro počty přesunů:
Průměrný počet přesunů
4
)
(
3 2
n
n
−
=
Maximální počet přesunů
2
)
(
3 2
n
n
−
=
Opět obě základní operace (srovnání a přesuny) mají kvadratickou složitost.
Závěr: Třídění přímou výměnou má časovou složitost
Θ(n2).
Implementace této metody třídění je velmi snadná. Program tvoří dva vnořené cykly. Jejich tělo
obsahuje podmíněný příkaz, jež zajišťuje operaci srovnání, a tří příkazy přiřazení, které realizují
vzájemnou výměnu sousedních prvků. Pro svoji jednoduchost je třídění přímou výměnou velmi
oblíbené. Používá se pro něj název bublinkové třídění. Toto označení je odvozeno od
skutečnosti, že prvky postupně jednotlivými výměnami „probublávají“ na svoji cílovou pozici.
Byly navrženy i některé modifikace metody, jež zlepšují její efektivitu v určitých situacích.
Uveďme dvě nejvýznamnější z nich.
Vezměme následující posloupnost:
3 1 9 2 8 4 5 7