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