Maximum and Minimum element of an array

 Maximum and minimum element of an array (Divide &  Conquer Method):

The problem is to find the maximum and minimum items in a set of n elements. A straightforward algorithm to accomplish this is given below:

            Algorithm StraightMaxMin(a,n,max,min)

            {

                        max=min=a[1]

                        for i=2 to n

                                    if a[i]>max

                                                max=a[i]

                                    endif

                                    if a[i]<min

                                                min=a[i]

                                    endif

                        endfor

            }

§  Analysis:

To analyse the complexity of the above mentioned algorithm, we concentrate on the number of element comparisons. It can be justified because the frequency count for other operations in this algorithm is of the same order as that for element comparisons. This algorithm requires 2(n-1) element comparisons in the best, average and worst case.

 Ø Improvement 1:

This above mentioned algorithm can be further improved by replacing the contents of the for loop by:

          if a[i]>max

                   max=a[i]

          endif

          else if a[i]<min

                                                min=a[i]

                                      endif

Now the best case occurs when the elements are in increasing order. The number of element comparisons in best case is n-1. The worst case occurs when the elements are in decreasing order. In that case, the number of comparisons are 2(n-1).

Ø Improvement 2:

The solution can be further improved by using a divide and conquer approach:

          Algorithm MaxMin(i,j,max,min)

/*a[1:n] is a global array. Parameters i and j are integers,1 ≤ i ≤ j ≤n. The effect is to set max and min to the largest and smallest values in a[i:j], respectively*/                                                                                                

{

                        if (i==j) then max=min=a[i]; // Small(P)

                        else if (i=j-1) then // Another Case of Small(P)

                        {

                                    if(a[i]<a[j]) then

                                    {

                                           max=a[j]

                                          min=a[i]

                                    }

                                    else

                                    {

                                               max=a[i]                                                                                                                               min=a[j]

                                    }

                        }

                        else

                        {

                                    // If P is not small, divide P into two sub-problems.                                                              // Find where to split the set.

                                                                                             

                                    //Solve the sub-problems.

                                   MaxMin(i,mid,max,min)                                                                                                      MaxMin(mid+1,j,max1,min1)

                                   // Combine the solutions.

                                   if(max<max1) then max=max1                                                                                              if(min>min1) then min=min1

                        }

            }

If T(n) represents the number of comparisons required to find minimum and maximum elements from an array of n elements, then the resulting recurrence relation is:

 

Hence, to find maximum and minimum element from an array of n elements, 3n/2-2 comparisons are required. Compared with the straightforward approach, divide and conquer approach is saving off 25% in the comparisons.