|
|
|
Aplety:
V metodě přímého i binárního vkládání jsme vždy brali jeden předem určený
prvek zdrojové posloupnosti a ten jsme vkládali do cílové posloupnosti (tj.
probírali jsme celou cílovou posloupnost). Metoda
přímého výběru je založena na opačném principu: ze zdrojové
posloupnosti vybereme vhodný prvek (uvažujeme tedy vlastně celou zdrojovou
posloupnost) a ten vložíme na předem přesně určené místo cílové
posloupnosti. Algoritmus
přímého výběru bude založen na následující myšlence: 1.
Najdeme ve zdrojové posloupnosti prvek s nejmenším klíčem. 2. Vyměníme ho s prvkem na první pozici. 3. Nyní je na první pozici nejmenší prvek z celé posloupnosti. Potřebujeme
utřídit zbytek posloupnosti, proto opakujeme tyto kroky se zbylými n-1
prvky, dokud je n>1. Příklad
1.3
Na
obrázku 1.3
vidíme postup třídění posloupnosti (3,
2, 17,
1, 8,
5) metodou přímého
výběru. Šipky naznačují výměny. Poznamenejme, že ve druhém kroku
nedojde k výměně prvků, neboť nejmenší prvek ze zdrojové posloupnosti je
právě na druhém místě; podobně nedojde k výměně v pátém kroku.
Obr.
1.3
Třídění přímým výběrem Procedura pro třídění přímým výběrem bývá obvykle uváděna ve tvaru procedure
PřímýVýběr; var
i,j,k: index; x:
prvek; begin for
i := 1 to n-1 do begin
{na první druhé,... místo} k
:= i; x
:= a[i];
{*} for
j := i+1 to n do
{najdi nejmenší} if
a[j].klíč < x.klíč then begin
k := j;
x := a[j];
{**} end; a[k]
:= a[i];
{prohoď ho s prvkem na i-tém místě} a[i]
:= x;
{***} end; end; Poněkud výhodnější může být následující varianta téže procedury, ve které ušetříme několik přesunů prvků: procedure
PřímýVýběr1; var
i,j,k: index; x:
prvek; begin for
i := 1 to n-1 do begin
{na první druhé,... místo} k
:= i; for
j := i+1 to n do
{najdi index nejmenšího} if
a[j].klíč < a[k].klíč then begin
k := j; end; x
:= a[k];
{prohoď nejmenší s prvkem na i-tém místě} a[k]
:= a[i]; a[i]
:= x; end; end; Analýza
třídění přímým výběrem
Pokud jde o počet porovnání klíčů, je tato metoda horší než přímý výběr. Počet porovnání totiž nezávisí na počátečním uspořádání prvků v poli, neboť v i-tém kroku vždy prohledáváme celé pole a od pozice i+1 do konce. To znamená, že počet porovnání je
Pokud jde o počet přesunů, záleží na tom, zda použijeme proceduru PřímýVýběr nebo PřímýVýběr1. V
případě procedury PřímýVýběr bude minimální počet přesunů
a to v případě, že pole je již uspořádané. Maximální počet přesunů nastane v případě, že pole je uspořádané v opačném pořadí. V tom případě se při každém průchodu vnějším cyklem provedou příkazy označené jednou a třemi hvězdičkami. Ty obsahují celkem 3 přesuny. Přiřazovací příkaz, označený dvěma hvězdičkami, se při i = 1 provede (n - 1)-krát, při dalším průchodu (n - 2)-krát, atd. (Při prvním průchodu se na poslední místo uložil největší prvek; ve druhém průchodu se začíná u druhého a skončí u předposledního prvku a přitom se na předposlední místo uloží druhý největší prvek atd.) Pro i > n/2 se již příkaz se dvěma hvězdičkami neprovádí, neboť pole je již srovnáno. Při
sčítání řady n-1 + n-2 + ... musíme rozlišit několik případů podle hodnoty n.
Dostaneme, že maximální počet přesunů bude Mmax = [n^2/2] kde [z] opět znamená celou část čísla z. Při stanovení průměrného počtu přesunů se předpokládá, že všechny možné permutace prvků pole a jsou stejně pravděpodobné. Lze ukázat, že průměrný počet přesunů bude přibližně roven n(ln n + g), kde g je Eulerova konstanta, g = 0,577... Použijeme-li proceduru PřímýVýběr1,
bude třeba v každém kroku 3 přesuny bez ohledu na uspořádání prvků,
tedy celkem 3(n-1) přesunů.
|
|
|
