SELECT
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
Robert W. Floyd a Ronald L. Rivest vyvinuli patrně nejdokonaleší verzi algoritmu s vynikajícími výsledky v průměru. Ve svém článku napsali: "Výsledky ukazují, že se SELECT v počet potřebných porovnání velmi blíží optimálnímu řešení."
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: rekurzívní 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
SELECT: procedure expose A.
parse arg L, R, K
do while R > L
if R - L > 600 then do
N = R - L + 1; I = K - L + 1; Z = LN(N)
S = TRUNC(0.5 * EXP(2 * Z / 3))
SD = TRUNC(0.5 * SQRT(Z * S * (N - S)/N) *,
SIGN(I - N/2))
LL = MAX(L, K - TRUNC(I * S / N) + SD)
RR = MIN(R, K + TRUNC((N - I) * S / N) + SD)
call SELECT LL, RR, K
end
T = A.K; I = L; J = R
W = A.L; A.L = A.K; A.K = W
if A.R > T
then do; W = A.R; A.R = A.L; A.L = W; end
do while I < J
W = A.I; A.I = A.J; A.J = W
I = I + 1; J = J - 1
do while A.I < T; I = I + 1; end
do while A.J > T; J = J - 1; end
end
if A.L = T
then do
W = A.L; A.L = A.J; A.J = W
end
else do
J = J + 1; W = A.J; A.J = A.R; A.R = W
end
if J <= K then L = J + 1
if K <= J then R = J - 1
end
return
EXP: procedure
parse arg Tr; numeric digits 3; Sr = 1; X = Tr
do R = 2 until Tr < 5E-3
Sr = Sr + Tr; Tr = Tr * X / R
end
return Sr
SQRT: procedure
parse arg X; numeric digits 3
if X < 0 then return -1
if X=0 then return 0
Y = 1
do until ABS(Yp - Y) <= 5E-3
Yp = Y; Y = (X / Yp + Yp) / 2
end
return Y
LN: procedure
parse arg X; numeric digits 3
M = (X + 1) / (X - 1); Ln = 1 / M
do J = 3 by 2
T = 1 / (J * M ** J)
if T < 5E-3 then leave
Ln = Ln + T
end
return 2 * Ln
|
SOUVISLOSTI
Literatura
Floyd R. W., Rivest R. L. Algorithm 489 The Algorithm SELECT - for Finding the ith Smallest of n Elements [M1]
CACM, March 1975, Vol. 18, No. 3, p. 173
Floyd R. W., Rivest R. L. Expected Time Bounds for Selection
CACM, March 1975, Vol. 18, No. 3, pp. 165-172
