I'm trying to find the second smallest element in an array of n elements using only n + ceil(lg n) - 2 comparisons. The hint in CLRS says to find the smallest element.
This takes n - 1 comparisons so I'm left with ceil(lg n) - 1 comparisons to find the second smallest, once I know the largest.
Any ideas?
Thanks,
bclayman
Let's say we've got a list a1...an with n being a power of 2.
First pair the elements up, let's say a1 with a2, a3 with a4 and so on, and compare them with each other. This gives you n/2 comparisons.
Advance all the winners to the next round, which only has n/2 elements now, and repeat the same process. This requires n/4 more comparisons.
Repeat the above until you've only got 1 element left, the ultimate winner. To get there you had to do n/2 + n/4 + ... + 1 = n-1 comparisons.
That's great but which one could be the second smallest? Well, it has to be one of the elements your winner had beaten along the way to the top. There are lg n such losers, so you need to compare them amongst each other to find the smallest (requiring a further lg n - 1 comparisons).
And the smallest of the losers is the second smallest overall.
It's easy to prove why the above method always finds the second smallest: since it's smaller than every element but the ultimate winner, it would win every round apart from the one against the champion.
If n isn't a power of 2, the process is almost exactly the same, except the list of losers will be as long as it would be for the next exact power of 2 which is why you end up with ceil(lg n).
Round class that contains the two elements being compared and a reference each to the Round objects they came from. Then from the winner you can walk the route back to the very first round the winner featured in. Of course that's an additional 2n memory slots but the question was only about the number of comparisons.Here is a basic implementation in JavaScript, not sure it fully respects your O() requirements in all cases though. The initial array will also affect the comparison count.
var elements = [ 12, 1 , 3, 4, 65, 7, -43, 8, 3, 8, 45, 2 ];
var nCompare = 0;
var smallest = elements[0], smaller = elements[0];
for(var i = 1; i < elements.length; ++i) {
++nCompare;
if(elements[i] < smaller) {
++nCompare;
if(elements[i] < smallest) {
smaller = smallest;
smallest = elements[i];
}
else
smaller = elements[i];
}
}
document.body.innerHTML = '<pre>\n' +
'Elements: [ ' + elements.join(', ') + ' ]\n' +
'# element: ' + elements.length + '\n' +
'\n' +
'Smallest: ' + smallest + '\n' +
'2nd smallest: ' + smaller + '\n' +
'# compare: ' + nCompare +
'</pre>';
Below is a solution with O(n) complexity in Java:
public class MainClass {
public static void main(String[] args) {
int[] a = { 4, 2, 8, -2, 56, 0 };
c(a);
}
private static void c(int[] a) {
int s = Integer.MAX_VALUE;
int ss = Integer.MAX_VALUE;
for (int i : a) {
if (i < s) {
ss = s;
s = i;
} else if (i < ss) {
ss = i;
}
}
System.out.println("smallest : " + s + " second smallest : " + ss);
}
}
Output : smallest : -2 second smallest : 0
I think their is no need to for cel(log n) -1 additional comparison as it can be done in O(n) only i.e in one scan with the help of an extra variable as given below:-
for(i,0,no_of_elem-1)
{
if(min>elem[i])
{
second_smallest=min;
min=elem[i];
}
}
You just store previous minimum in a variable as that will be your answer after scanning all elements.
smallestandsecondsmallest; set them both to values much higher than anything in the array. Then loop through the array, adjusting the values of the two variables based on the array element you're currently looking at.lgterm seems to suggest some kind of divide and conquer approach.