FINDING THE MAXIMUM AND MINIMUM
The problem is to find the maximum and minimum items in a set of n
elements.
1.
Algorithm for straight forward maximum and
minimum
StraightMaxMin(a,n,max,min)
//
set max to the maximum and min to the minimum of a[1:n].
{
max := min := a[1];
for i := 2 to n do
{
if(a[i] > max) then max := a[i];
if(a[i] > min) then min := a[i];
}
}
Analyzing the
Straight Forward Method
In
analyzing the time complexity of this algorithm, we have to concentrate on the
number of element comparisons. This algorithm requires 2(n-1) element
comparisons in the best, average, and worst cases. An immediate improvement is
possible by realizing that the comparison a[i] < min is necessary only when
a[i]>max is false.
Now
the Best case occurs when the elements are in increasing order. The number of
element comparisons is n-1. The worst case occurs when the element are in
decreasing order. In this case number of comparisons is 2(n-1).
FINDING THE MAXIMUM AND MINIMUM using DIVIDE
AND CONQUER Strategy
·
What is DIVIDE AND CONQUER Strategy?
Given
a function to compute on n inputs the divide-and-conquer
strategy suggest splitting the inputs into k distinct subsets, 1 < K ≤ n, yielding k sub problems.
These Sub problems must be solved, and then a method must be found to combine
sub solutions into a solution of the whole. If the Sub problems are still
relatively large, then the divide-and-conquer
strategy can possibly be reapplied. Often the sub problems resulting from a divide-and-conquer
design are the same type as the original problem. For those cases the
reapplication of the divide-and-conquer
principle is naturally expressed by a recursive algorithm. Now smaller sub
problems of the same kind are generated until eventually sub problems that are
small enough to be solved without splitting are produced.
A divide-and-conquer
algorithm
for this problem would proceed as follows:
Let P = (n,a[i],….,a[j]) denote an arbitrary instance of the problem.
Here n is the number of elements in the list a[i],….,a[j] and we are interested
in finding the maximum and minimum of this list. Let small(P) be true when n ≤ 2. In this case, the maximum and
minimum are a[i] if n = 1. If n = 2, the problem can be solved by making one
comparison.
If
the list has more than two elements, P has to be divided into smaller
instances. For example, we might divide P into the two instances P1 =
(n/2,a[1],….,a[n/2]) and P2 = (n - n/2,a[n/2 + 1],….,a[n]). After having
divided P into two smaller sub problems, we can solve them by recursively
invoking the same divide and conquer algorithm.
Now
the question is How can we combine the Solutions for P1 and P2 to obtain the
solution for P? If MAX(P) and MIN(P) are the maximum and minimum of the
elements of P, then MAX(P) is the larger of MAX(P1) and MAX(P2) also MIN(P) is
the smaller of MIN(P1) and MIN(P2).
MaxMin
is a recursive algorithm that finds the maximum and minimum of the set of
elements {a(i),a(i+1),…,a(j)}. The situation of set sizes one (i=j) and two
(i=j-1) are handled separately. For sets containing more than two elements, the
midpoint is determined and two new sub problems are generated. When the maxima
and minima of this sub problems are determined, the two maxima are compared and
the two minima are compared to achieve the solution for the entire set.
The
procedure is initially invoked by the statement MaxMin(1,n,x,y). for this
algorithm each node has four items of information: i, j, max, min. Suppose we
simaulate MaxMin on the following nine elements:
a:
[1] [2]
[3] [4] [5]
[6] [7] [8]
[9]
22
13 -5 -8 15
60 17 31 47
A
good way of keeping track of recursive calls is to build a tree by adding a
node each time a new call is made. On the array a[ ] above, the following tree
is produced.
We see that the root node contains 1
and 9 as the values of i and j corresponding to the initial call to MaxMin.
This execution produces two new call to MaxMin, where i and j have the values
1, 5 and 6, 9, and thus split the set into two subsets of the same size. From
the tree we can immediately see that the maximum depth of recursion is four
(including the first call).
1.
Algorithm for maximum and minimum using divide-and-conquer
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].
{
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 sub-problems.
//
Find where to split the set.
mid
:= ( i + j )/2;
//
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;
}
}
Complexity:
Now what is the number of element comparisons needed for MaxMin? If
T(n) represents this number, then the resulting recurrence relation is
0 n=1
T(n) = 1 n=2
T(n/2)
+ T(n/2) + 2 n>2
When n is a power of two, n = 2k
-for some positive integer k,
then
T(n) = 2T(n/2) + 2
= 2(2T(n/4) + 2) + 2
= 4T(n/4) + 4 + 2
.
.
.
= 2k-1 T(2) + ∑(1≤i≤k-1) 2k
= 2k-1 +
2k – 2
= 3n/2 – 2 = O(n)
Note that 3n/2 – 2 is the best, average,
worst case number of comparison when n is a power of two.
Comparisons
with Straight Forward Method:
Compared
with the 2n – 2 comparisons for the Straight Forward method, this is a saving
of 25% in comparisons. It can be shown that no algorithm based on comparisons
uses less than 3n/2 – 2 comparisons.
Implementation in Java
public class MaxMin {
static MaxMin m=new MaxMin();
static int max,min;
public static void main(String ar[])
{
int a[]={10,12,9,7,15,11,1};
MaxMin.max=MaxMin.min=a[0];
int[] getMaxMin=m.MaxMin(a, 0, a.length-1, a[0], a[0]);
System.out.println("Max : "+getMaxMin[0]+"\nMin : "+getMaxMin[1]);
}
public int[] MaxMin(int[] a,int i,int j,int max,int min)
{
int mid,max1,min1;
int result[]=new int[2];
//Small(P)
if (i==j) { max = min = a[i]; }
else if (i==j-1) // Another case of Small(P)
{
if (a[i] < a[j]) { this.max = getMax(this.max,a[j]); this.min = getMin(this.min,a[i]); }
else { this.max = getMax(this.max,a[i]); this.min = getMin(this.min,a[j]); }
}
else
{
// if P is not small, divide P into sub-problems.
// Find where to split the set.
mid = ( i + j )/2;
// Solve the sub-problems.
max1=min1=a[mid+1];
MaxMin( a, i, mid, max, min );
MaxMin( a, mid+1, j, max1, min1 );
// Combine the solutions.
if (this.max < max1) this.max = max1;
if (this.min > min1) this.min = min1;
}
result[0]=this.max; result[1]=this.min;
return result;
}
public static int getMax(int i,int j)
{
if(i>j) return i;
else return j;
}
public static int getMin(int i,int j)
{
if(i>j) return j;
else return i;
}
}
Output:
