Maximum and minimum of an array using minimum number of comparisons | GeeksforGeeks
Write a C function to return minimum and maximum in an array. You program should make minimum number of comparisons.
METHOD 3 (Compare in Pairs)
If n is odd then initialize min and max as first element.
If n is even then initialize min and max as minimum and maximum of the first two elements respectively.
For rest of the elements, pick them in pairs and compare their maximum and minimum with max and min respectively.
http://www.geeksforgeeks.org/maximum-and-minimum-in-a-square-matrix/
Read full article from Maximum and minimum of an array using minimum number of comparisons | GeeksforGeeks
Write a C function to return minimum and maximum in an array. You program should make minimum number of comparisons.
METHOD 3 (Compare in Pairs)
If n is odd then initialize min and max as first element.
If n is even then initialize min and max as minimum and maximum of the first two elements respectively.
For rest of the elements, pick them in pairs and compare their maximum and minimum with max and min respectively.
struct
pair getMinMax(
int
arr[],
int
n)
{
struct
pair minmax;
int
i;
/* If array has even number of elements then
initialize the first two elements as minimum and
maximum */
if
(n%2 == 0)
{
if
(arr[0] > arr[1])
{
minmax.max = arr[0];
minmax.min = arr[1];
}
else
{
minmax.min = arr[0];
minmax.max = arr[1];
}
i = 2;
/* set the startung index for loop */
}
/* If array has odd number of elements then
initialize the first element as minimum and
maximum */
else
{
minmax.min = arr[0];
minmax.max = arr[0];
i = 1;
/* set the startung index for loop */
}
/* In the while loop, pick elements in pair and
compare the pair with max and min so far */
while
(i < n-1)
{
if
(arr[i] > arr[i+1])
{
if
(arr[i] > minmax.max)
minmax.max = arr[i];
if
(arr[i+1] < minmax.min)
minmax.min = arr[i+1];
}
else
{
if
(arr[i+1] > minmax.max)
minmax.max = arr[i+1];
if
(arr[i] < minmax.min)
minmax.min = arr[i];
}
i += 2;
/* Increment the index by 2 as two
elements are processed in loop */
}
return
minmax;
}
Total number of comparisons: Different for even and odd n, see below:
If n is odd: 3*(n-1)/2 If n is even: 1 Initial comparison for initializing min and max, and 3(n-2)/2 comparisons for rest of the elements = 1 + 3*(n-2)/2 = 3n/2 -2
METHOD 2 (Tournament Method)
Divide the array into two parts and compare the maximums and minimums of the the two parts to get the maximum and the minimum of the the whole array.
Divide the array into two parts and compare the maximums and minimums of the the two parts to get the maximum and the minimum of the the whole array.
Pair MaxMin(array, array_size) if array_size = 1 return element as both max and min else if arry_size = 2 one comparison to determine max and min return that pair else /* array_size > 2 */ recur for max and min of left half recur for max and min of right half one comparison determines true max of the two candidates one comparison determines true min of the two candidates return the pair of max and min
struct
pair getMinMax(
int
arr[],
int
low,
int
high)
{
struct
pair minmax, mml, mmr;
int
mid;
/* If there is only on element */
if
(low == high)
{
minmax.max = arr[low];
minmax.min = arr[low];
return
minmax;
}
/* If there are two elements */
if
(high == low + 1)
{
if
(arr[low] > arr[high])
{
minmax.max = arr[low];
minmax.min = arr[high];
}
else
{
minmax.max = arr[high];
minmax.min = arr[low];
}
return
minmax;
}
/* If there are more than 2 elements */
mid = (low + high)/2;
mml = getMinMax(arr, low, mid);
mmr = getMinMax(arr, mid+1, high);
/* compare minimums of two parts*/
if
(mml.min < mmr.min)
minmax.min = mml.min;
else
minmax.min = mmr.min;
/* compare maximums of two parts*/
if
(mml.max > mmr.max)
minmax.max = mml.max;
else
minmax.max = mmr.max;
return
minmax;
}
Total number of comparisons: let number of comparisons be T(n). T(n) can be written as follows:
Algorithmic Paradigm: Divide and Conquer
Algorithmic Paradigm: Divide and Conquer
T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2 T(2) = 1 T(1) = 0
If n is a power of 2, then we can write T(n) as:
T(n) = 2T(n/2) + 2
After solving above recursion, we get
T(n) = 3/2n -2
Thus, the approach does 3/2n -2 comparisons if n is a power of 2. And it does more than 3/2n -2 comparisons if n is not a power of 2.
Second and third approaches make equal number of comparisons when n is a power of 2.
In general, method 3 seems to be the best.
http://www.geeksforgeeks.org/maximum-and-minimum-in-a-square-matrix/
Given a square matrix of order n*n, find the maximum and minimum from the matrix given.
Select two elements from the matrix one from the start of a row of the matrix another from the end of the same row of the matrix, compare them and next compare smaller of them to the minimum of the matrix and larger of them to the maximum of the matrix. We can see that for two elements we need 3 compare so for traversing whole of the matrix we need total of 3/2 n2 comparisons.
void
maxMin(
int
arr[][MAX],
int
n)
{
int
min = INT_MAX;
int
max = INT_MIN;
// Traverses rows one by one
for
(
int
i = 0; i < n; i++)
{
for
(
int
j = 0; j <= n/2; j++)
{
// Compare elements from beginning
// and end of current row
if
(arr[i][j] > arr[i][n-j-1])
{
if
(min > arr[i][n-j-1])
min = arr[i][n-j-1];
if
(max< arr[i][j])
max = arr[i][j];
}
else
{
if
(min > arr[i][j])
min = arr[i][j];
if
(max< arr[i][n-j-1])
max = arr[i][n-j-1];
}
}
}
cout <<
"Maximum = "
<< max;
<<
", Minimum = "
<< min;
}