MODIFIND
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
Running time of my
MODIFIND is O(N**2) in the worst case and O(N) in the average case.
It needs fewer swaps than FIND and SELECT.
PRACTICE
Algorithms
MODIFIND and
SELECT are almost always faster than
FIND.
SELECT needs fewer comparison 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: nonrecursive 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
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

CONNECTIONS
Literature
Hoare C. A. R. Proof of a Program: FIND
CACM, Vol 14, No. 1, January 1971, pp. 3945
Wirth N. Algorithms and data strucure
New Jersey, Prentice Hall, Inc., Engelwood Cliffs, 1986
Zabrodsky V. Variace na klasicke tema
Elektronika (former Czech computer journal), No. 6, 1992, pp. 3334