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

last modified 8th August 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic.

mail