Find

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
The FIND algorithm was proposed by C. A. R. Hoare. It was the first fast average-time algorithm. Its worst-case running time is O(N**2) on an input array of N elements and its expected running time is O(N).

PRACTICE
Algorithms MODIFIND and SELECT are almost 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: 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

 


FIND: procedure expose A.
parse arg N, K
L = 1; R = N
do while L < R
  X = A.K; I = L; J = R
  do until I > J
    do while A.I < X; I = I + 1; end
    do while X < A.J; J = J - 1; end
    if I <= J
      then do
        W = A.I; A.I = A.J; A.J = W
        I = I + 1; J =J - 1
      end
  end
  if J < K then L = I
  if K < I then R = J
end
return A.K

 

CONNECTIONS
Selection Problem
     Smallest and largest simultaneously
     Modifind
     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 Rexx page Mail

last modified 11th September 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic