Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



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 >fornext 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 forloop 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 email]



