e an algorithm to find the maximum element in an unsorted array many comparisons
ID: 3600578 • Letter: E
Question
e an algorithm to find the maximum element in an unsorted array many comparisons are done in the best case? 1) a) Writ ci How many comparisons are done in the average case? d) How many comparisons are done in the worst case? 2) Do the same as part 1) for the minimum of an array a) Write an algorithm that find the maximum and the minimum of an array. b) How many comparisons are done in the worst case? c) Can you do better? (1.5n is the best), a) Write an algorithm that finds the maximum and the 2-nd maximum. b) How many comparisons are done in the worst case? c) Can you do better? 4) a) Think of a way to find the median of an unordered array b) About how many comparisons will have to be done? 5)Explanation / Answer
1a.ans- Linear search algorithm
#include <stdio.h>
// C function to find maximum in arr[] of size n
int largest(int arr[], int n)
{
int i;
// Initialize maximum element
int max = arr[0];
// Traverse array elements from second and
// compare every element with current max
for (i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
return max;
}
int main()
{
int arr[] = {10, 324, 45, 90};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Largest in given array is %d", largest(arr, n));
return 0;
}
1b.ans- N comparison, suppose we have an array[10,20,4] then it will compare 10 with 20 and 4,again it will compare 20 with 4 son total compares will be 3 which is equal to N(size of array).
1c.ans- N comparison, suppose we have an array[10,20,4] then it will compare 10 with 20 and 4,again it will compare 20 with 4 son total compares will be 3 which is equal to N(size of array).
1d.ans- N comparison, suppose we have an array[10,20,4] then it will compare 10 with 20 and 4,again it will compare 20 with 4 son total compares will be 3 which is equal to N(size of array).
2a.ans-linear search
#include <stdio.h>
// C function to find maximum in arr[] of size n
int minimum(int arr[], int n)
{
int i;
// Initialize min element
int min = arr[0];
// Traverse array elements from second and
// compare every element with current max
for (i = 1; i < n; i++)
if (arr[i] < min)
min = arr[i];
return min;
}
int main()
{
int arr[] = {10, 324, 45, 90};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Largest in given array is %d", minimum(arr, n));
return 0;
}
2b.ans- N comparison, suppose we have an array[10,20,4] then it will compare 10 with 20 and 4,again it will compare 20 with 4 son total compares will be 3 which is equal to N(size of array) and then it will return 4 as smallest element.
2c.ans-N comparison, suppose we have an array[10,20,4] then it will compare 10 with 20 and 4,again it will compare 20 with 4 son total compares will be 3 which is equal to N(size of array) and then it will return 4 as smallest element.
2d.ans-N comparison, suppose we have an array[10,20,4] then it will compare 10 with 20 and 4,again it will compare 20 with 4 son total compares will be 3 which is equal to N(size of array) and then it will return 4 as smallest element.
3a.ans- simple linear search
/* structure is used to return two values from minMax() */
#include<stdio.h>
struct pair
{
int min;
int max;
};
struct pair getMinMax(int arr[], int n)
{
struct pair minmax;
int i;
/*If there is only one element then return it as min and max both*/
if (n == 1)
{
minmax.max = arr[0];
minmax.min = arr[0];
return minmax;
}
/* If there are more than one elements, then initialize min
and max*/
if (arr[0] > arr[1])
{
minmax.max = arr[0];
minmax.min = arr[1];
}
else
{
minmax.max = arr[1];
minmax.min = arr[0];
}
for (i = 2; i<n; i++)
{
if (arr[i] > minmax.max)
minmax.max = arr[i];
else if (arr[i] < minmax.min)
minmax.min = arr[i];
}
return minmax;
}
/* Driver program to test above function */
int main()
{
int arr[] = {1000, 11, 445, 1, 330, 3000};
int arr_size = 6;
struct pair minmax = getMinMax (arr, arr_size);
printf("nMinimum element is %d", minmax.min);
printf("nMaximum element is %d", minmax.max);
getchar();
}
3b.ans-In this method, total number of comparisons is 1 + 2(n-2) in worst case.
3c.ans- In this method, total number of comparisons is 1 + n – 2 in best case. so we don't have to care about 1.5n .
4a.ans- linear search
#include<tsdio.h>
#include<limit.h>
int max(int arr[],int n)
{
int i;
int max, secondMax;
max = secondMax = INT_MIN;
for(i = 0; i < count; i++){
if(array[i] > max){
secondMax = max;
max = array[i];
} else if (array[i] > secondMax
&& array[i] < max){
secondMax = array[i];
}
}
/* Printing Maximum And Second Maximum element */
printf("Maximum Element : %d Second Maximum Element: %d", max, secondMax);
}
int main()
{
int arr[] = {10, 324, 45, 90};
int n = sizeof(arr)/sizeof(arr[0]);
max(arr, n);
return 0;
}
4b.ans-N comparison
4c.ans-this is the most efficient one
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.