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 average-time version. They say: "The results show that SELECT is at least near-optimal 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 < 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

CONNECTIONS
Selection Problem
Smallest and largest simultaneously
Find
Modifind
Power - real exponent

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. 165-172
Zabrodsky V., FIND, SELECT, MODIFIND

 cover contents index main page