Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: second largest element in a matrix
Replies: 32   Last Post: May 5, 2013 10:31 AM

 Messages: [ Previous | Next ]
 Bruno Luong Posts: 9,822 Registered: 7/26/08
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

Date Subject Author
9/18/08 Oluwa KuIse
9/19/08 stephanie
9/19/08 Steven Lord
9/19/08 Oluwa KuIse
9/19/08 Pekka
9/19/08 Oluwa KuIse
9/21/08 Greg Heath
9/24/08 Walter Roberson
3/4/09 Justin
4/6/09 Bruno Luong
4/6/09 Jos
4/6/09 Bruno Luong
4/6/09 Bruno Luong
4/6/09 mike zander
4/7/09 Bruno Luong
4/7/09 Bruno Luong
4/3/09 Paul
11/7/12 sssbi2009@gmail.com
11/19/12 dpb
4/3/09 Paul
4/3/09 mike zander
4/3/09 mike zander
4/3/09 mike zander
4/3/09 Walter Roberson
4/3/09 mike zander
5/4/13 tilindg1@gmail.com
5/4/13 Nasser Abbasi
5/4/13 dpb
5/5/13 Nasser Abbasi
5/5/13 dpb
5/5/13 Bruno Luong
5/5/13 Nasser Abbasi
5/5/13 Bruno Luong