Program to Find Maximum and Minimum Number of an Array using Tournament Method

  • Write a program to find maximum and minimum element of an array using tournament method.
  • Write a C program to find max and min element using linear search.

Given an integer array of size N. We have to find the maximum and minimum element of of given array by using linear search and by using tournament method.
For Example :
Input Array : 7 3 5 1 10 6 23 9 4
Maximum Element : 23
Minimum Element : 1

Method 1 : By using Linear Search
Algorithm to find maximum and minimum element using simple linear search.
Let "inputArray" be an integer array of size N.
  • Initialize max and min value by first element of array.
  • Using a loop, traverse inputArray from index 0 to N-1.
  • For every element inputArray[i], compare it with current max and min.
  • If inputArray[i] > max then set max = inputArray[i].
  • Else If inputArray[i] < min then set min = inputArray[i].
Time Complexity : O(n)

C program to find max and min number using linear search.

#include <stdio.h>

/* Checks whether a is odd or not. Returns 1 
if a is Odd number otherwise 0 */
int isOdd(int a){
   return a%2; 
}

/*Seperates Even and Odd Numbers of an array. first all Even and 
then all Odd numbers. This approach is similar to partition step 
of quick sort */
void seperateOddEven(int *array, int size){
    int temp, left = 0, right = size-1;
    while(right > left){
     /* traverse from left to right till we find a Odd number */
     while(!isOdd(array[left]))
         left++;
     /* traverse from right to left till we find an Even number */
     while(isOdd(array[right]))
         right--;
     
     if(left < right){
            /* Swap array[left] and array[right] */
            temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }
    }
 
}

int main(){
    int array[10] = {2, 7, 5, 10, 13, 20, 14, 0, 7, 3}; 
    int i;
    
    seperateOddEven(array, 10);
    
    for(i = 0; i < 10; i++){
     printf("%d ", array[i]);
    }

    return 0;
}
Output
2 0 14 10 20 13 5 7 7 3
Method 1 : By using Tournament Method (Divide and Conquer)
Algorithm to find maximum and minimum element using tournament method.
Let "inputArray" be an integer array of size N.
  • Initialize leftIndex and rightIndex to first and last element of array.
  • Initialize max and min value by first element of array(left Most element).
  • If size of inputArray is 1, the return.
  • Divide the inputArray into two equal sub arrays. Let it be leftArray and rightArray.
  • Recursively calculate the max and min element of leftArray and rightArray.
  • To find the max element of inputArray, take the maximum of leftArray max and rightArray max.
  • To find the min element of inputArray, take the minimum of leftArray min and rightArray min.
Time Complexity : O(n)

C program to find max and min number using tournament method.

#include <stdio.h>

/* This structure is used to return 
 two values from a function */
struct MaxMin {
    int min;
    int max;
}; 

/* Implementation of tournament method using recursion */
struct MaxMin getMinMax(int *array, int left, int right) {
    struct MaxMin result, resultLeft, resultRight;       
    int mid;
   
    result.max = array[left];
    result.min = array[left];
  
    if(right == left)
        return result; 
    /* Split the array into two equal sub arrays and 
    recursively find max and min in both sub array */
    mid = (left + right)/2;  
    resultLeft = getMinMax(array, left, mid);
    resultRight = getMinMax(array, mid+1, right);  
   
    /* Take the maximum of both sub array */
    if (resultLeft.max > resultRight.max)
       result.max = resultLeft.max;
    else
       result.max = resultRight.max;    
    
    /* Take the minimum of both sub array */
    if (resultLeft.min < resultRight.min)
       result.min = resultLeft.min;
    else
       result.min = resultRight.min;     
 
    /* Return the maximum and minimum of whole array */
    return result;
}

int main(){
    int array[9] = {7, 3, 9, 7, -3, -1, 4, 0, 7}; 

    struct MaxMin maxmin = getMinMax(array, 0, 8); 
    
    printf("Maximum = %d\n", maxmin.max);
    printf("Minimum = %d\n", maxmin.min);
    
    return 0;
}
Output
Maximum = 9
Minimum = -3
Posted by
Labels: ,