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
Literature
Baudoin C., Meyer B. Méthodes de programmation
Edition Eyrolles 61, Bd Saint-Germain Paris 1978
