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.

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.

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


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
  if J < K then L = I
  if K < I then R = J
return A.K


Selection Problem
     Smallest and largest simultaneously

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