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.
Klíčovou záležitostí je volba prvku as. Optimální by bylo zvolit ho tak, aby vzniklé části A a B
měly stejnou velikost (stejný počet prvků). To by znamenalo najít prvek, jehož hodnota je
uprostřed hodnot všech prvků. Nalezení takového prvku je ale natolik časově náročné, že by se
to celkově nevyplatilo. Proto se volí mnohem jednodušší způsob - vezme se prvek, který v poli
je uprostřed.
V popisu algoritmu použijeme značení:
a – je jméno pole s tříděnými prvky
k,l – jsou indexy počátku a konce části pole, která je právě tříděna
r – je index prvku, který je uprostřed tříděné části
i,j – jsou průběžné indexy používané pro procházení polem ve směrech odpředu a odzadu
Popis algoritmu
1. Počáteční krok
Na počátku právě tříděnou částí bude celé pole, tj. nastavíme
1
0
−
=
=
n
l
k
.
2. Třídící krok
Najdeme index prvku, který je uprostřed tříděné části pole
2
l
k
s
+
=
Přesněji řečeno, pokud tříděná část má sudý počet prvků, pak je to index prvního ze dvou prvků,
které jsou uprostřed. Prvek pole s tímto indexem as si uložíme do proměnné, kterou si označíme
x.
Průběžné indexy nastavíme na začátek a konec právě tříděné části
l
j
k
i
=
=
Nyní procházíme tříděnou část směrem dozadu, zvětšujeme index i, tak dlouho, až najdeme
prvek, pro který platí
x
a
i ≥
.
Následně procházíme tříděnou část směrem dopředu, snižujeme index j, tak dlouho, až najdeme
prvek, pro který platí
x
a
j ≤
.
Prvky ai a aj mezi sebou vyměníme a následně zvýšíme hodnotu indexu i a snížíme hodnotu
indexu j
1
1
−
=
+
=
j
j
i
i
Proces hledání a výměn provádíme tak dlouho, dokud nenastane i>j. V tomto okamžiku je
buďto i=j+1, pak pole je rozděleno na dvě části: