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: Sorting problem
Replies: 6   Last Post: Aug 15, 1996 6:18 PM

 Messages: [ Previous | Next ]
 Hans Olsson Posts: 14 Registered: 12/7/04
Re: Sorting problem
Posted: Aug 14, 1996 4:48 AM

In article <321137B6.6C90@swansea.ac.uk>,
Mark Smart <m.smart@swansea.ac.uk> wrote:
>Does anyone have experience with the following problem? I have
>a matrix of geometric positions
>
>A=
>[x1 y1 z1;
>x2 y2 z2;] etc
>
>I wish to sort it in the following way:
>
>1. Firstly according to vector magnitude. This is easy:
>
>[y,index]=sort(sum((A.*A)')');
>A=A(index,:)
>
>2. Then all vectors of the same magnitude must be sorted with
>respect to x, then y, then z. For example, if
>A=
>[1 0 0;
>2 1 0;
>1 3 1;
>0 0 1];
>
>the first sort produces
>A=[
>1 0 1; % magn =sqrt(2)
>0 1 1; % =sqrt(2)
>1 1 0; % magn =sqrt(2)
>2 1 0; % =sqrt(5)
>1 3 1;] % =sqrt(11)
>
>whilst the final output should be
>
>A=[
>0 1 1;
>1 0 1;
>1 1 0;
>2 1 0;
>1 3 1;]
>
>Is there an efficient way of doing this? It may be trivial but
>I've racked my brains and can't think of a solution without many
>for-next loops.

I'm not sure that this is the most effient solution in matlab, but
the problem seems to be to sort vector with respect to x then y then z.
Provided that sort is stable (I believe it is, but I'm not sure)
you could use something like this for that part:
(Forward radix sort is more fun, but it would be a bit longer but
faster).

function A=sortmulti(A)
% Radix sort. Stupid but at least vectorized.
for i=size(A,2):-1:1
[m,I]=sort(A(:,i));
A=A(I,:);
end;

---
Main routine could be as complex as:

[y,index]=sort(sum((A.*A)')');
A=A(index,:);
n=length(y);
y2=[-inf;y;inf];
% Find sequences of several identical magnitudes
Istart=find((y2(1:n)~=y2(2:n+1))&(y2(2:n+1)==y2(3:n+2)));
Istop=find((y2(1:n)==y2(2:n+1))&(y2(2:n+1)~=y2(3:n+2)));

% Handle each sequence at a time.
for i=1:length(Istart)
A(Istart(i):Istop(i),:)=sortmulti(A(Istart(i):Istop(i),:));
end;

----
Or as simple as:

A=[sum((A.*A)')',A];
A=sortmulti(A);
A=A(:,2:4);

So you only need 1 for-loop provided that sort really is stable
(i.e. preserves the order of items with identical keys).

--
// http://www.dna.lth.se/home/Hans_Olsson/
// Hans.Olsson@dna.lth.se [Please no junk e-mail]

Date Subject Author
8/14/96 Hans Olsson
8/14/96 O. Haas
8/14/96 Pope P. Britt
8/15/96 Roger Moss
8/15/96 Pope P. Britt
8/15/96 John Polking