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.
Po rozdělení pole
na dvě části se
stejný postup
rekurzivně
aplikuje na obě
části.
s
, ovšem pokud jsem již indexem j nedosáhli počátku pole (tj. j=k).
Pokud nyní pro indexy i, j platí podmínka (i > j) proces hledání a výměn ukončíme, neboť je pole rozděleno na dvě části.
− 36 −
Příklad. Tříděné pole nechť obsahuje
3 4 1
Na začátku je k = 0, l = 2.
Vypočítáme
1
2
2
0
=
+
=
s
, x = a1 = 4
a položíme i = 0, j = 2.
Po hledání zleva je i = 1, neboť je a1≥x (4≥4), a po hledání zprava je j=2 neboť je a2≤x (1≤4). Po
výměně prvků a1 a a2 a přičtení 1 k indexu i a odečtení je 1 od indexu j je rozdělení pole
3 1 | 4 ,
neboť hodnoty indexů jsou nyní i = 2, j = 1.
Druhá z možností je, že bude platit i=j+2. Pak z pole se vydělí opět dvě části, mezi nimiž je ale
ještě jeden prvek, jehož hodnota je stejná, jako je v proměnné x:
Příklad. Tříděné pole nechť obsahuje
5 3 4 1
Na začátku je k = 0, l = 3.
Vypočítáme
1
2
3
0
=
+
=
s
, x = a1 = 3
a položíme i = 0, j = 3.
Po hledání zleva je i = 0, neboť a0≥x (5≥3), a pohledání zprava je j=3, neboť a3≤x (1≤3). Po
výměně bude pole
1 3 4 5
a nové hodnoty indexů i = 1, j = 2.
Po pokračování hledání zleva bude i = 1, neboť a1≥x (3≥3), a po pokračování hledání zprava
bude j=2, neboť a1≤x (3≤3). Po výměně (prvek a1 se vymění sám se sebou) bude pole
1 3 4 5
a nové hodnoty indexů i = 2, j = 1. Tudíž výsledné rozdělení pole je