Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

you have 32 numbers. What is the least number of comparison needed to find the 2nd smallest out of them.

As per me it 61 comparsisons are required. Compare first two number in list. Assign largest and second largest to them based on comparison. Now compare rest 30 numbers with two of them and assign largest and second largest based on comparison. So for rest of 30 numbers we have to do 2 comparison for each number . this answer is 30*2 + 1 = 61. Can 61 be reduced?

share|improve this question

3 Answers 3

up vote 8 down vote accepted

I happen to remember this one from my algorithms class. Take your list of 32 numbers and try to find the smallest number. Compare the first and second numbers, the third and fourth, etc. until you reduce the list by half and repeat. It will take 31 comparisons to find the smallest number as each comparison eliminates one possibility.

Once this has been complete, make a list of the numbers the smallest number has been compared to. There should be 5. It will take 4 comparisons to find the smallest of these 5 numbers, for a total of 35 comparisons.

share|improve this answer
    
Near-simulpost! You were 10 seconds after me (by my clock) with the same algorithm and answer. :) –  Charles Apr 27 at 5:41
    
@Charles Yep, it happens. Did you really just upvote your own answer by the way? I saw it as posted 7 seconds ago and it already had an upvote. –  Mike Apr 27 at 5:42
    
Not me, must have been someone else. I'll give you +1, though -- I can't fault your answer, of course. –  Charles Apr 27 at 5:44
    
@Charles Strange. Ah well, +1 to yours as well. –  Mike Apr 27 at 5:55
    
@Mike one can't upvote one's post :-) by the way I think it will help if you explain why the smallest element will be compared only to $5$ other numbers. (I know it's $\log_2 32$ though :-P) –  Ant Apr 27 at 15:32

35 comparisons are optimal. Pair off the numbers and test them against each other. Take the winners, the winners' winners, and so forth to find the maximal element; this takes 31 comparisons in all. Now the maximal element was compared against five other elements, and the second-largest element is precisely the largest of these five. You can find it in four comparisons, for a total of 35 comparisons.

share|improve this answer
    
Should that last sentence read "... for a total of $35$ comparisons."? –  John Bentin Apr 27 at 5:44
    
@JohnBentin: Good call, I fixed the typo. –  Charles Apr 27 at 5:45
3  
How do you prove that 35 is optimal? –  bof Apr 27 at 9:47

From Wikipedia article on Selection Algorithm:

In The Art of Computer Programming, Donald E. Knuth discussed a number of lower bounds for the number of comparisons required to locate the t smallest entries of an unorganized list of n items (using only comparisons). There is a trivial lower bound of n − 1 for the minimum or maximum entry. To see this, consider a tournament where each game represents one comparison. Since every player except the winner of the tournament must lose a game before we know the winner, we have a lower bound of n − 1 comparisons.

Think of it as a tournament. To find out the winner (think of it as the smallest number), we need to rule out every other player. For this to happen, every other player will need to have undergone the selection procedure. So, to find the winner from a total of 32 players, it will require at least 31 selections. To generalize, it will require at least $n-1$ comparisons to find the lowest number from a set of $n$ numbers.

share|improve this answer
1  
We're trying to find the second-smallest, not the smallest. –  user2357112 Apr 27 at 15:10
1  
@user2357112: I agree that this answer does not directly answer the question as stated, but the intuition from this answer applies. The second-smallest number is the second-place finisher in the tournament. How many games do you have to play to find out who finishes second in a tournament? –  Eric Lippert Apr 27 at 15:54
1  
@EricLippert: 31 for a 32-player single-elimination tournament, but this isn't enough to determine the second-best entrant, because maybe the second-best lost to the best in an early round. A double-elimination tournament would do it (ignoring the fact that games don't perfectly reflect skill), but it'd take 61 rounds. In any case, I was more addressing the fact that Amal may have misread the question, since the answer specifically talks about finding the lowest number. –  user2357112 Apr 27 at 16:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.