Find second smallest number

Not too difficult.

What's the search time of an array? Let's say I have A[100] and I want A[5]. How long does that take?

Hopefully this hint will help you out.

I would modify the smallest number algorithm to be something like this:



In words, while searching for the smallest value in the array we know that when we find a new smallest value then the old smallest value has become the second smallest value (for an example of this case, run the algorithm on the array [2, 1]). We also need one more case: if the value we are looking at is not the smallest but it happens to be smaller than the current second smallest (for an example of this case, run the algorithm on the array [1, 2]).

I have never encountered this problem, by off the top of my head: When you want to find the smallest number, you do:



The last time the CODEBLOCK1 is executed, the "min" takes its final value. So,logically, the number that was "min" that time is the second smallest. So it becomes:



EDIT: My wrong. I missed the second special case Colin Jeanne mentioned.

I am afraid that your solutions will not meet the requirements since it will, in worst case, run in 2n - 3 comparations. The worst case would be when the smallest and second smallest number is the two first ones. In this case the algorithem would do two comparations/item.

I could be wrong on this one but I think not.

Feel free to bash me ;)

Nytegard: Either I don't get what you mean, or you don't get what I mean. Getting an element of an array is constant time, of course, but how does that help me here?

Colin Jeanne & mikeman: that was my first idea, too, but I think Wc-duck has it right there: that would do 2n-3 > n + ... comparisons on an array like 1,9,8,...,2.

Other ideas?

What if we take Colin's code and reverse it? Instead of:




we have:



The reason for the nested if is that, if a number is not smaller from the 2nd-smallest, then of course it's not smaller from the smallest so there's no reason to perform that comparison.

Quote:

Original post by Amarth Nytegard: Either I don't get what you mean, or you don't get what I mean. Getting an element of an array is constant time, of course, but how does that help me here? Colin Jeanne & mikeman: that was my first idea, too, but I think Wc-duck has it right there: that would do 2n-3 > n + ... comparisons on an array like 1,9,8,...,2. Other ideas?

Not giving you the answer, only hints. Anyways, the algorithm they provided above isn't the most efficient.

Here's another hint

123456789135791591912359252

*Edit*

Correct sequence should be, I guess I need to leave work and get some sleep.

12345678913579159151235232

[Edited by - Nytegard on January 10, 2007 9:25:09 PM]

Reversing it would not matter since all to the right of the two elements are bigger it will compare each two times.

Nytegard, I too have problem understanding what you first comment(search time of an array) has to do with the requirements of the problem( n + ceil(log2(n)) - 2 comparisons in the worst case).

Quote:

Reversing it would not matter since all to the right of the two elements are bigger it will compare each two times.

No it won't. Let's say the current smallest numbers is 1 and 2, and we need to compare 5. In the reversed algorith, it will compare it only with the 2nd-smallest(2), and not proceed to the nested if.

Perhaps a sort then grab the second element? I have no idea how many operations a sort takes.

Quote:

Original post by mikeman Nytegard, I too have problem understanding what you first comment(search time of an array) has to do with the requirements of the problem( n + ceil(log2(n)) - 2 comparisons in the worst case).

Mikeman, I'm keeping these hints a little obscure because it does involve schoolwork to an extent, and the answer he's after is in his book.

If you have an array, 1, 2, 3, 4, 5
You don't compare 1 to 2, 3, 4, and 5.

While traversing the array is technically the fastest way to get the smallest element in an unsorted array, it's not the fastest way to get the second smallest element, or the third smallest. For each extra element you want to find, be it the third, or the fourth, it becomes more complex. That's not to say that sorting the array is necessary, but it's a step in the right direction.

Quote:

Original post by mikeman No it won't. Let's say the current smallest numbers is 1 and 2, and we need to compare 5. In the reversed algorith, it will compare it only with the 2nd-smallest(2), and not proceed to the nested if.

Ok then... lets sort the list with biggest first and I think that you are in a bit of trouble.

P.S. After some googling I think I got it but as said earlier Its kind of related to schoolwork so Ill keep it to myself for now ;)

I forgot to say that the hints are actually quite good!

Quote:

Original post by Wc-duck Quote: Original post by mikeman No it won't. Let's say the current smallest numbers is 1 and 2, and we need to compare 5. In the reversed algorith, it will compare it only with the 2nd-smallest(2), and not proceed to the nested if. Ok then... lets sort the list with biggest first and I think that you are in a bit of trouble. P.S. After some googling I think I got it but as said earlier Its kind of related to schoolwork so Ill keep it to myself for now ;)

Yes, you're right.

I don't see why we should be so secretive about it, he said it's not for schoolwork, just something he read in one of his books.

Some thing to read maby?

http://en.wikipedia.org/wiki/Selection_algorithm

It might be worth considering that log2(n) often comes up when you're working with binary trees.

If I got it right, there's a standard library algorithm that does the hard part (although you might need/want to resynthesize it somewhat). (Don't even mouseover the link if you don't want a spoiler!)

I think Zahlman is on the right track, except that the standard library doesn't seem to bound the number of comparisons as tightly as it could and the algorithm does need to be slightly modifed to get the theoretically minimum we're going for.

Mmmm... I need some more pushing. I'm not reading the links yet, though.

Dumbing down random selection might be the solution, but since it's defined after the exercise, that feels kind of cheating. I suppose there is another way.

(mostly writing towards Nytegard, here) You need some sort of semi-sorting, is that what you're aiming at? Only the first couple of steps from one of the other algorithms? I don't really see how you could make some sort of half-sorted array from it, though. Do I need to think the 'heap' way or the 'quicksort partition' way, or is it something entirely else?

Perhaps another question to push me around (hopefully in the right direction): what are the memory constraints on the algorithm I'm searching? Constant, or a function of n?

That sequence around the start is really puzzling me, btw. If there's some sort of recursion at play in it, I don't see it.

I'm feeling kind of dumb at the moment. Don't let that bother you. Now that you've started the thread this way, don't just give the answer, let me search a bit more, please :).