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.
Zapamatujeme si pozici prvku 7
Srovnáme s 1
→ zapamatujeme si pozici prvku 1
Srovnáme s 2, 8, 4, 5, 3, 9
Zapamatovaná je pozice prvku 1, ten vyměníme s prvním prvkem 7
1 | 7 2 8 4 5 3 9
Další krok – zapamatujeme si pozici prvku 7
Srovnáme s 2
→ zapamatujeme si pozici prvku 2
Srovnáme s 8, 4, 5, 3, 9
Zapamatovaná je pozice prvku 2, ten vyměníme s prvním prvkem 7
1 2 | 7 8 4 5 3 9
Atd.
Složitost metody Uvedený algoritmus třídění je založen na operacích výběru a výměny. Vezměme nejprve
operaci výběru. Nechť počet prvků v nesetříděné části je k. Abychom našli její nejmenší prvek,
potřebujeme k tomu k-1 srovnání. Neboť počínaje druhým prvkem v nesetříděné části postupně
srovnáváme všechny její prvky až po poslední prvek, vždy s právě zapamatovaným prvkem.
Délky nesetříděných částí jsou v jednotlivých krocích n, n-1, …,2. Odtud dostáváme:
Celkový počet srovnání
2
2
)
1
(
1
...
)
2
(
)
1
(
2
n
n
n
n
n
n
−
=
−
=
+
+
−
+
−
=
Nyní uvažujme operaci výměny vybraného, nejmenšího prvku s prvním prvkem nesetříděné
části. Ta v každém kroku proběhne jen jednou. Teoreticky vzato když nastane případ, že
nejmenší prvek je hned na začátku nesetříděné části, nemusela by tato operace vůbec
proběhnout. Nicméně je jednodušší a i efektivnější případně vyměnit prvek sám se sebou, než
před každou výměnou ověřovat, zda nenastal případ, že výměna není potřebná. Třídících kroků
je n-1 a s ohledem na to, že jedna výměna vyžaduje tři přesuny, odtud dostáváme
Celkový počet přesunů
)
1
(