
Re: second largest element in a matrix
Posted:
Apr 6, 2009 2:29 PM


Walter Roberson <roberson@hushmail.com> wrote in message <STjCk.14881$Il.4473@newsfe09.iad>... > Oluwa KuIse wrote: > > > Can anyone pls tell me how I can find the second (or third) largest element in a > > matrix AND its position. > > The algorithms that people gave all ran in at least time N (length of the > matrix) times the number of largest elements to be found. > > I was interested to discover a couple of weeks ago that there are simple > algorithms that for any fixed number L of largest elements, are able to > execute a single pass over the array and using L (or was it L+1 ?) > temporary storage locations, find the L largest values. > > Unfortunately in the short time I put into reading the algorithm, I did > not understand how the algorithm worked, so I cannot describe it here. > And I no longer recall where I found the algorithm  though either as > a reference here or on wikipedia are the two most likely candidates.
While searching something related to a stable quicksort I bump into this article: http://en.wikipedia.org/wiki/Selection_algorithm
The interesting part are "Optimised Sorting algorithm" and "Tournament algorithm".
Bruno

