Path: news.mathworks.com!not-for-mail
From: "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
Newsgroups: comp.soft-sys.matlab
Subject: Re: The N largest values of an M x 1 matrix
Date: Thu, 3 Jan 2008 20:49:41 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 40
Message-ID: <fljhp5$cvr$1@fred.mathworks.com>
References: <57537254-3f7e-43e4-8fc4-75d8de63b3d6@s8g2000prg.googlegroups.com>  <7222b5d8-b1b3-425c-be43-ac349257c5e7@e23g2000prf.googlegroups.com>
Reply-To: "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1199393381 13307 172.30.248.38 (3 Jan 2008 20:49:41 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Thu, 3 Jan 2008 20:49:41 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:444253


Palle Uldenborg <palle.uldenborg@gmail.com> wrote in message 
<7222b5d8-b1b3-425c-be43-
ac349257c5e7@e23g2000prf.googlegroups.com>...
> > Palle Uldenborg <palle.uldenb...@gmail.com> wrote in message
>......
> > > I would like to find the indexes of the N largest elements of an   M x
> > > 1 matrix.......
> I am interested in situations such as N=5 and M=100000, so I think
> that I could gain from a matlab function that did some kind of partial
> sorting.
>                        Niels
---------
  For values as high as M = 100000 and as small as N = 5, it is true that a 
sort operation may be relatively inefficient, since it is an order M*log(M) 
algorithm.  I have not heard of a matlab "partial sort" function, so you would 
probably have to replace the sort with some kind of carefully thought out for-
loop type algorithm.

  One strategy might be to construct an order M*N algorithm along the 
following lines using the max function.  Let a be the M x 1 vector.   Then do:

 q = M:-1:1; % Start with all of vector a in current list
 p = zeros(N,1); % Allocate indices storage
 for r = N:-1:1
  [ignore,s] = max(a(q)); % Find the current maximum
  p(r) = q(s); % Store its index
  q(s) = []; % Drop it from the current list
 end

The N-element vector a(p) will have the N largest elements of a and p will 
have their indices.

  It is clear, however, that the number N would not have to be very large 
before this method would be far more inefficient than doing a straight sort.

  [Note: Between Jos and Roberson you probably have the essential equivalent 
of the above, but I'll include this anyhow.]

Roger Stafford