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. Budeme opět třídit posloupnost
7 1 2 8 4 5 3 9
Postupně srovnáváme sousední prvky
Časová složitost
této metody
třídění je
kvadratická.
Třídíme
vzájemnou
výměnou dvou
sousedních
prvků.
− 26 −
Srovnání 7 s 1
→ výměna
1 7 2 8 4 5 3 9
Srovnání 7 s 2
→ výměna
1 2 7 8 4 5 3 9
Srovnání 7 s 8
→ ve správném pořadí
Srovnání 8 s 4
→ výměna
1 2 7 4 8 5 3 9
Srovnání 8 s 5
→ výměna
1 2 7 4 5 8 3 9
Srovnání 8 s 3
→ výměna
1 2 7 4 5 3 8 9
Srovnání 8 s 9
→ ve správném pořadí
V dalším průchodu budeme srovnávat už jen 7 prvků
1 2 7 4 5 3 8 | 9
Srovnání 1 s 2
→ ve správném pořadí
Srovnání 2 s 7
→ ve správném pořadí
Srovnání 7 s 4
→ výměna
1 2 4 7 5 3 8 | 9
Srovnání 7 s 5
→ výměna
1 2 4 5 7 3 8 | 9
Srovnání 7 s 3
→ výměna
1 2 4 5 3 7 8 | 9
Srovnání 7 s 8
→ ve správném pořadí
V dalším průchodu budeme srovnávat už jen 6 prvků
1 2 4 5 3 7 | 8 9
Srovnání 1 s 2
→ ve správném pořadí
Atd.
Složitost metody Uvedený algoritmus třídění je založen na operacích srovnání a výměny. Vezměme opět nejprve
operaci srovnání. V prvním průchodu se prochází všech n prvků, což reprezentuje srovnání n-1
sousedních dvojic. V druhém průchodu se prochází n-1 prvků, tedy n-2 srovnávaných dvojic.
V posledním průchodu má procházená část dva prvky, tedy se provede jen jedno srovnání.
Odtud dostáváme