I've been thinking about this homework question for a bit now. Given an number array of size n, design an algorithm that will find the high and and low values with at most 1.5n comparisons.
My first try was
int high=0
int low= Number.MaxValue //problem statement is unclear on what type of number to use
Number numList[0 . . n] //number array, assuming unsorted
for (i=0, i < n, i++) {
if (numList[i] > high)
high = numList[i]
else if (numList[i] < low)
low = numList[i]
}
My problem is each iteration of the loop has one of three possibilities:
So for an entire array traversal, a maximum of 2n comparisons can be made, which is a far cry from the problem maximum requirement of 1.5n comparisons.
Claim: Every comparison-based algorithm for finding both the minimum and the maximum of n elements requires at least (3n/2)-2 comparisons.
For each pair, there are three comparisons: first among the elements of the pair and the other two with min and max. Total number of comparisons = 3 * (n-1) / 2 (If n is odd) or 3n/2 – 2 (If n is even).
4.
This is a question I had during an interview and I found the answer with a small hint from the interviewer which was "How do you compare two numbers?" (it really helped).
Here is the explanation:
Lets say I have 100 numbers (you can easily replace it by n but it work better for the example if n is an even number). What I do is that I split it into 50 lists of 2 numbers. For each couple I make one comparison and I'm done (which makes 50 comparisons by now) then I just have to find the minimum of the minimums (which is 49 comparisons) and the maximum of the maximums (which is 49 comparisons as well) such that we have to make 49+49+50=148 comparisons. We're done !
Remark: to find the minimum we proceed as follow (in pseudo code):
n = myList.size();
min = myList[0];
for (int i(1); i<n-1; i++)
{
if (min>myList[i]) min = myList[i];
}
return min;
And we find it in (n-1) comparisons. The code is almost the same for maximum.
Start with a pairs of numbers and find local min and max (n/2 comparisons). Next, find global max from n/2 local maxes (n/2 comparisons), and similarly global min from local mins (n/2 comparisons). Total comparisons: 3*n/2 !
For i in 0 to n/2: #n/2 comparisons
if x[2*i]>x[2*i+1]:
swap(x,2*i,2*i+1)
global_min = min( x[0], x[2], ...) # n/2 comparisons
global_max = max( x[1], x[3], ...) # n/2 comparisons
Note that the above solution changes the array. Alternate solution:
Initialize min and max
For i = 0 to n/2:
if x[2*i]<x[2*i+1]:
if x[2*i]< min:
min = x[2*i]
if x[2*i+1]> max:
max = x[2*i+1]
else:
if x[2*i+1]< min:
min = x[2*i+1]
if x[2*i]> max:
max = x[2*i]
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With