Smallest and largest simultaneously

Find smallest and largest elements of the numeric array in the same time.

Simple algorithm MINANDMAX uses for finding of minimum and maximum simultaneously about 2*N comparisons.

Unit: nonrecursive internal function
Global variables: an array A. of numeric elements
Parameter: a positive integer N - size of A.
Returns: Values of the minimum and maximum separated by blank

MINANDMAX: procedure expose A.
parse arg N
Min = A.1; Max = A.1
do J = 2 to N
  if A.J < Min then Min = A.J
    else if A.J > Max then Max = A.J
return Min Max


Textbooks say that the following algorithm MINIMAX is more efficient. Its time complexity is FORMAT(3*N/2-2,,0) comparisons. Attention: the function has to be called by statement say MINIMAX(1,N) with two paramwters.

MINIMAX: procedure expose A.
parse arg J, N
if N = J then return A.J A.J
if N = J + 1
  then if A.J < A.N
         then return A.J A.N
         else return A.N A.J
  else do
    parse value MINIMAX(J, J + 1) with Min1 Max1
    parse value MINIMAX(J + 2, N) with Min2 Max2
    return MIN(Min1, Min2) MAX(Max1, Max2)


But there is a implementation limit on the nesting of subroutine levels. Non-recursive version of MINIMAX with the time complexity FORMAT(3*N/2,,0) follows


NON_RECURSIVE_MINIMAX: procedure expose A.
parse arg N
push 1 N; Min = A.1; Max = A.1
do while QUEUED() > 0
  pull J R
    when R = J
      then do
        Min = MIN(A.J, Min)
        Max = MAX(A.J, Max)
    when R = J + 1
      then do
        if A.J < A.R
          then do
            Min = MIN(A.J, Min)
            Max = MAX(A.R, Max)
          else do
            Min = MIN(A.R, Min)
            Max = MAX(A.J, Max)
          push J (J + 1)
          if J+2 <= R then push (J + 2) R
return Min Max


For N=50000 the MINANDMAX(N) needs 99989 comparisons and NON_RECURSIVE_MINIMAX(N) needs only 75000 comparisons. But MINANDMAX computes 5.66 seconds and NON_RECURSIVE_MINIMAX 43.33 seconds!


Technique: Recursion Elimination
Selection Problem

Baudoin C., Meyer B. Méthodes de programmation
Edition Eyrolles 61, Bd Saint-Germain Paris 1978

cover contents index main page

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