Anonymous 7843 wrote:

> Jaspreet <(E-Mail Removed)> wrote:

> > Just thinking what is a good way of getting second highest value in an

> > integer array. One method I know of is to make the 1st pass through the

> > array and find the highest number. In the second pass we can find the

> > highest number which is less than the number we obtained in the 1st

> > pass.

> >

> > However there has to be a better and more efficient way of doing this.

> > Please just let me know some hints and I would try it on my own in C.

>

> Just make one pass through the array. Keep two variables,

> which track:

>

> * highest so far

> * 2nd highest so far

>

> As you iterate through the array, when you find a new "highest"

> one, move the previous "highest" to "2nd highest." Plus, if

> you happen upon an element that his higher than the 2nd highest

> but not as high as the first, make that the 2nd highest without

> disturbing the highest.
For specifically the second highest, I will endorse this algorithm.

You are hardly going to do better.

> As you extend the idea to finding (for example) 490th highest

> element it becomes quite a bit less efficient, since it's

> basically an insertion sort.
Well, for the mth highest this algorithm is basically O(m^2*n).

However, there exists an O(n) "kth rank" algorithm. See:

http://www.nist.gov/dads/HTML/select.html
http://en.wikipedia.org/wiki/Selection_algorithm
Unfortunately, I have not seen a really good explanation for why the

implementation truly matches the analysis. However, if you think about

it, its not hard to see that they are right. The "group of 5" are not

adjacent sub-elements, but in fact seperated by n/5 offsets, and then

each group is just shifted down one element at a time, with some number

of tail entries with only 4 elements each. In this way, the median of

5 steps are O(n) and the final partitioning does not require additional

movement operations.

> At some point it's better to just sort the array and then everything is

> positioned perfectly.
Well, O(n) < O(n*ln(n)), so sorting is only going to be better if you

have many "kth element requests" relative to the number of insert or

delete operations.

--

Paul Hsieh

http://www.pobox.com/~qed/
http://bstring.sf.net/