MODIFIND
PROBLÉM
Nalezení K-tého nejmenšího z N prvků: Je dáno pole
A., obsahující N (různých) prvků, a přirozené číslo K, 1<=K<=N, určete K-tý nejmenší prvek A. a přerovnejte pole tak, aby tento prvek byl v A.K a všechny prvky s indexy menšími než K neměly větší hodnotu než A.K a všechny prvky s indexy většími než K neměly hodnotu menší než A.K.
ALGORITMUS
Časová složitost mého algoritmu je stejná jako u algoritmu FIND, tj. O(N) v průměrném a O(N**2) v nejhorším případě. Tento algoritmus ale vyžaduje nejméně výměn prvků v porovnání s algoritmy FIND a SELECT.
PRAXE
Algoritmy
MODIFIND a
SELECT jsou téměř vždy rychlejší než
FIND.
SELECT potřebuje méně operací porovnání než
MODIFIND;
MODIFIND potřebuje méně operací výměn prvků než
SELECT. Následující tabulka uvádí průměrnou dobu výpočtu
10. testů naměřenou algoritmům
FIND,
MODIFIND, a
SELECT při určování mediánu z
10000 prvků - řetězců délky
L<=6 (jen čísla),
L<=7,
L<=500:
| Porovnání algoritmů |
| Algoritmus |
L <= 6 |
L <= 7 |
L <= 500 |
| FIND |
0.957 |
1.475 |
4.104 |
| MODIFIND |
0.929 |
1.212 |
1.476 |
| SELECT |
0.602 |
0.828 |
0.985 |
IMPLEMENTACE
Jednotka: vnitřní funkce
Globální proměnné: pole A. libovolných prvků
Parametry: přirozené číslo N - počet prvků v A., přirozené číslo K, 1<=K<=N
Výsledek: Přerovnání vstupního pole tak, že v A.K je uložena tatáž hodnota, jakou bychom tu našli, kdyby bylo pole utříděno, L<=I<=K implikuje A.I<=A.K, a K<=I<=R implikuje A.I>=A.K
Vrací: A.K
MODIFIND: procedure expose A.
parse arg N, K
L = 1; R = N
do while L < R
X = A.K; I = L; J = R
do until J < K | K < I
do while A.I < X; I = I + 1; end
do while X < A.J; J = J - 1; end
W = A.I; A.I = A.J; A.J = W
I = I + 1; J = J - 1
end
if J < K then L = I
if K < I then R = J
end
return A.K
|
SOUVISLOSTI
Literatura
Hoare C. A. R. Proof of a Program: FIND
CACM, Vol 14, No. 1, January 1971, pp. 39-45
Wirth N. Algorithms and data strucure
New Jersey, Prentice Hall, Inc., Engelwood Cliffs, 1986
Zábrodský V. Variace na klasické téma
Elektronika, č. 6, 1992, s. 33-34
