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
Selection Problem
Smallest and largest simultaneously
Find
Select

Literature
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
Zabrodsky V. Variace na klasicke tema
Elektronika (former Czech computer journal), No. 6, 1992, pp. 33-34

 cover contents index main page