I need help with the following assignment: Another problem of element selection
ID: 3739734 • Letter: I
Question
I need help with the following assignment:
Another problem of element selection is to find both the largest and the smallest elements in a list of n elements at the same time.
1)Present a single brute-force algorithm for the problem and describe the key idea behind your solution. Determine and show the range for the number of element comparisons performed.
2)Develop a single recursive divide-and-conquer algorithm for the problem and describe the key idea behind your solution. Establish and solve the recurrence relation for the number of element comparisons performed.
3)Additionally, test the both of the following algorithms in Java
These algorithms have to be done WITHOUT the use of sorting
***please help. I really can't think of an algorithm that doesn't use sorting and I also have a very shaky understanding of determining the range of the number of comparisons, as well as establishing and solving the reccurrence relationship***
Explanation / Answer
Brute force algorithm:
Approach:
Iterate on the array and get the maximum number.
Steps:
1. Create two variables named max and min.
2. Iterate over the list and compare each number with the min and the max
2.a if the number is greater than the max update max,
2.b if the number is less than the min update the min.
3. Output min and max values
In this brute force solution the number of comparison is 2*n, where n is the number of elements
Recursive divide-and-conquer algorithm
Approach:
If you want to get result from same function(recursive) for both min and max, then create a structure for the pair of min and max
struct pair{
int min;
int max;
}
Algorithm:
struct pair getMinMax(int arr[], int n)
{
declare variable of type pair named minmax
define counter 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];
}
Operate on pair, if first value of array is greater than second then min becoes arr[1] and max becomes arr[0], or vice versa
if (arr[0] > arr[1])
{
minmax.max = arr[0];
minmax.min = arr[1];
}
else
{
minmax.max = arr[1];
minmax.min = arr[0];
}
Iterate on rest of the number array, with counter i=2
if (arr[i] > minmax.max)
minmax.max = arr[i];
else if (arr[i] < minmax.min)
minmax.min = arr[i];
return minmax variable
}
Number of comparisons: 1 + 2(n-2) in worst case and 1 + n – 2 in best case.