Select
PROBLEM
The selection problem can be stated as follows: given an array A. of N elements and an integer K, 1<=K<=N, determine the Kth smallest element of A. and rearrange the array in such a way that this element is placed in A.K and all elements with subscripts lower than K have values not
larger than A.K and all elements with subscripts greater than K have values not smaller than this.
ALGORITHM
Robert W. Floyd and Ronald L. Rivest have developed an improved averagetime version. They say: "The results show that SELECT is at least nearoptimal with respect to the number of comparisons used."
PRACTICE
Algorithms
MODIFIND and
SELECT are always faster than
FIND;
SELECT needs fewer comparisons than
MODIFIND;
MODIFIND needs fewer swaps than
SELECT. The average time over 10 trials required by
FIND,
MODIFIND, and
SELECT to determine the median of 10000 elements (strings) of length
L<=6 (only numbers),
L<=7,
L<=500 was found experimentally

Selection problem  Comparisons of Algorithms 

Algorithm 
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 
IMPLEMENTATION
Unit: recursive internal function
Global variables: the array A. of arbitrary elements
Parameters: a positive integer N  number of elements in A., a positive integer K such that 1<=K<=N
Result: Reordering of input array such that A.K has the value it would have if A. were sorted, L<=I<=K will imply A.I<=A.K, and K<=I<=R will imply A.I>=A.K
Returns: 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 A.K
EXP: procedure
parse arg Tr; numeric digits 3; Sr = 1; X = Tr
do R = 2 until Tr < 5E3
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) <= 5E3
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 < 5E3 then leave
Ln = Ln + T
end
return 2 * Ln

CONNECTIONS
Literature
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. 165172