Minimum number of comparisons to find the minimum and maximum

In this article, we will learn how to find the minimum number of comparisons to find the minimum and maximum elements of an array and derive a general formula for it.

The formula for the minimum number of comparisons to find the minimum and the maximum elements is ( 3n / 2 ) – 2 where n is the size of the array.

Let’s see how to derive this formula. We are assuming length of the array to be even.

First, we perform the following operation on the array.

1. Set i = 0 and j = n – 1 ( Assuming array to be zero – indexed ).
2. Perform the following operation while i < j
   • if array[i] > array[j]
     1. swap( array[i] , array[j] )
   • i = i + 1
   • j = j – 1

The above step requires n/2 comparisons. We are comparing the ith element from the start and ith element from last and placing the smaller element on a smaller index.

By doing this we split the array into 2 parts.

After swapping, the element at index i ( i < n/2 ) is smaller than the element at index n – i. Thus, the minimum element must lie in the first half of the array and the maximum element lie in the second half.

Hence, we can find the smallest element of the array by traversing from index 0 to (n-1)/2.

Number of comparisons to find minimum element of the array = n/ 2 – 1

The ‘-1’ is included because initially we can assume the first element to be minimum and then compare it with the rest of the elements.

Similarly, we can find the largest element of the array by traversing from index (n-1)/2+1 to n-1.

Number of comparisons to find maximum element of the array = n / 2 – 1

Total number of Comparision = Number of Comparisons to perform swapping + Number of comparisons to find minimum element + Number of Comparisons to find maximum element

Total number of Comparisons = n/2 + n/2 – 1 + n/2 – 1 = (3n)/2 – 2

See the following program for better understanding

#include<iostream>
using namespace std;

int main()
{
    // c will count the number of comparisons
    int c = 0;
    int n = 10;
    int array[] = {1,5,3,4,7,10,29,2,0,3};
    int i,j;
    i = 0;
    j = n - 1;
    
    while(i<j){
    	++c;
    	if(array[i]>array[j]){
    		swap(array[i], array[j]);
		}
		++i;
		--j;
	}
	
	int minimum,maximum;
	minimum = array[0];
	for(i=1;i<=(n-1)/2;++i){
		++c;
		if(minimum>array[i]){
			minimum = array[i];
		}
	}
	
	maximum = array[n-1];
	for(i=(n-1)/2+1;i<=n-2;++i){
		++c;
		if(maximum<array[i]){
			maximum = array[i];
		}
	}
    
    cout<<"Minimum: "<<minimum<<endl
    	<<"Maximum: "<<maximum<<endl
    	<<"Number of Comparisions: "<<c<<endl
    	<<"Number of Comparisions by Formula: "<<(3*n)/2-2<<endl;
    
}