Finding Second Smallest Element in Array

Question

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

Answer 1

Let's say we've got a list a₁...a_n with n being a power of 2.

First pair the elements up, let's say a₁ with a₂, a₃ with a₄ 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).

Answer 2

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>';