Max and Min Finding
Here our problem is to find the minimum and maximum items in a set of n elements. We will see two methods here first one is iterative version and the next one uses divide and conquer strategy to solve the problem.
Iterative Algorithm:
MinMax(A,n)
{
max = min = A[0];
for(i = 1; i <n; i++}
{
if(A[i] > max)
max = A[i];
if(A[i] < min}
min = A[i];
}
}
The above algorithm requires 2(n-1) comparison in worst, best, and average cases. The comparison A[i] < min is needed only when A[i] > max is not true. If We replace the content inside the for loop by
if(A[i] >1nax)
max = A[i];
else if(A[i] < min)
m.i_n = A[i];
Then the best case occurs when the elements are in increasing order with (n-1) comparisons and worst case occurs when elements are in decreasing order with 2(n-1) comparisons. For the average case A[i] > max is about half of the time so number of comparisons is 3n/2 — 1.
We can clearly conclude that the time complexity is O[n].
C Program For Mini Max Search
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 1000
void MinMax(int *arr, int l, int h, int *max, int *min)
{
int max1, min1;
if (l == h) { // case I - only one item
*max = *min = arr[0];
}
else if (l == h - 1) { // case II - when there are two elements
if (arr[l] > arr[h])
{
*max = arr[l];
*min = arr[h];
}
else {
*max = arr[h];
*min = arr[l];
}
}
else { // case - III
int mid = (l + h) / 2; // Divide
MinMax(arr, l, mid, max , min); // conquer
MinMax(arr, mid+1, h, &max1 , &min1); //conquer
if(*max < max1) *max = max1; //combine
if(*min > min1) *min = min1; //combine
}
}
int main(int argc, char const *argv[])
{
int arr[SIZE], n;
clock_t start, end;
double total_time = 0.00;
int min, max;
printf("Enter number of elements : ");
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
arr[i] = rand() % 1000;
}
start = clock();
MinMax(arr, 0, n-1, &max, &min);
end = clock();
printf("Min element : %d\nMax element : %d\n", min, max);
total_time += (double)(end - start) / CLOCKS_PER_SEC;
printf("Execution time : %f seconds", total_time);
return 0;
}
Post A Comment:
0 comments so far,add yours