MODIFIND

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

Zabrodsky V. FIND, SELECT, MODIFIND