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 :).

Quote:Original post by Amarth
(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?

A link has already been posted above with the algorithm that you're after.

Quote: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?

Well, you have to take into consideration what the question asked was, and how to approach it. What were you asked to do? Were you asked to sort the entire array? If not, why spend excess time doing that? *Edited* As for my first post, what would happen if you knew for a fact your second smallest element was at position A[2]? You'd have an O(1) access time of the second element. The question being, how do you get it there?

Take sorting for example. Certain sorting algorithms are inexpensive to insert elements, but extremely expensive to retrieve elements. Some are better at retrieving elements, but expensive to insert. Some ways to sort are inexpensive to retrieve and insert elements, but are horrible when you take into consideration the memory required. The right algorithm for the job.

Quote:
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.

As for the sequence, as I've stated, it could be wrong on some ends, as I wrote it up quickly while at work, and might not have proof read it as much as I should have, but it you look at the first 2 steps in it, you should get the idea of how the rest of the pattern works. Also, the sequence could be different depending how you implemented the algorithm. For the most part, it should give you the answer you're after. Try breaking the pattern up, and moving it onto different lines and moving the parts around some.

[Edited by - Nytegard on January 10, 2007 9:27:11 PM]

You're going for a strict bound on the number of comparisons, so that should rule out randomized algorithms. Randomized algorithms generally have good average performance but poor worst case performance (if there was some way to make it so every case had good performance, what would be the point in choosing things randomly?).

I have some sort of idea, which might be isomorphic to the solution I'm trying to find, or a step in the right direction. It might also be totally wrong. Also, I haven't worked it out fully yet.

Split the given array in pairs, as with the min/max search, and discard the bigger ones of each of these pairs. Divide the remaining smaller ones into new pairs, doing the same thing. This will eventually yield you the minimum in n-1 comparisons, I believe. Now, the second smallest number has to be one of the numbers 'beaten' by the smallest one. There are at most (exactly?) ceil(log2(n)) such numbers, right? So, we can find the smallest among these in ceil(log2(n)) - 1.

Now I only need to find some spiffy way to stick the numbers in an array so that it's clear which numbers are compared to each other. I think it might be something heap-like, but I can't really visualize it.

If you don't mind using extra memory, you could create separate containers for each element in the array to track the 'beaten' elements for each element. That would technically solve the problem posed in the exercise. I think you could even be clever with this and allocate all the needed extra memory in advance.

For a step in the right direction of solving the problem in place, study the algorithm associated with Zahlman's link. That algorithm will have a lower bound on the number of comparisons that is higher than the amount you're searching for, but it suggests a method that I think would be a very elegant solution.

Quote:Original post by Amarth
...

If you like programming problems like that try topcoder.com/tc. They would consider this a very easy problem.

I think Nytegard didn't really understand the problem. Amarth asked about
getting the second smallest number with n + lgn - 2 comparisons in worst case.
This is a strict requirements and He's not looking for O(n). Radomized
selection algorithm doesn't apply here.

Amarth's latest reply is kind of my thought. But I haven't figured it out yet.

Quote:Original post by Anonymous Poster
I think Nytegard didn't really understand the problem. Amarth asked about
getting the second smallest number with n + lgn - 2 comparisons in worst case.
This is a strict requirements and He's not looking for O(n). Radomized
selection algorithm doesn't apply here.

Amarth's latest reply is kind of my thought. But I haven't figured it out yet.

yes, the restriction is important, and that's what I want to know to. thanks!