Smallest and largest simultaneously

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

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

IMPLEMENTATION
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
end
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)
  end

 

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
  select
    when R = J
      then do
        Min = MIN(A.J, Min)
        Max = MAX(A.J, Max)
      end
    when R = J + 1
      then do
        if A.J < A.R
          then do
            Min = MIN(A.J, Min)
            Max = MAX(A.R, Max)
          end
          else do
            Min = MIN(A.R, Min)
            Max = MAX(A.J, Max)
          end
      end
    otherwise
          push J (J + 1)
          if J+2 <= R then push (J + 2) R
  end
end
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!

 

CONNECTIONS
Technique: Recursion Elimination
Selection Problem
     Find
     Modifind
     Select

Literature
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.

mail