Sort a matrix with another matrix

Question

Suppose I have a matrix A and I sort the rows of this matrix. How do I replicate the same ordering on a matrix B (same size of course)?

E.g.

A = rand(3,4);
[val ind] = sort(A,2);
B = rand(3,4);
%// Reorder the elements of B according to the reordering of A

This is the best I've come up with

m = size(A,1);
B = B(bsxfun(@plus,(ind-1)*m,(1:m)'));

Out of curiosity, any alternatives?

Update: Jonas' excellent solution profiled on 2008a (XP):

n = n

0.048524       1.4632       1.4791        1.195       1.0662        1.108       1.0082      0.96335      0.93155      0.90532      0.88976

n = 2m

0.63202       1.3029       1.1112       1.0501      0.94703      0.92847      0.90411       0.8849       0.8667      0.92098      0.85569

It just goes to show that loops aren't anathema to MATLAB programmers anymore thanks to JITA (perhaps).

Lol .. it took me a second to realize you were referring to another language .. was wondering what esoteric MATLAB syntax I was looking at! — Jacob, Apr 20 '10 at 23:00

score 17 · Accepted Answer · edited Jun 27 '16 at 07:40

A somewhat clearer way to do this is to use a loop

A = rand(3,4);
B = rand(3,4);
[sortedA,ind] = sort(A,2);

for r = 1:size(A,1)
   B(r,:) = B(r,ind(r,:));
end

Interestingly, the loop version is faster for small (<12 rows) and large (>~700 rows) square arrays (r2010a, OS X). The more columns there are relative to rows, the better the loop performs.

Here's the code I quickly hacked up for testing:

siz = 10:100:1010;
tt = zeros(100,2,length(siz));

for s = siz
    for k = 1:100

        A = rand(s,1*s);
        B = rand(s,1*s);
        [sortedA,ind] = sort(A,2);

        tic;
        for r = 1:size(A,1)
            B(r,:) = B(r,ind(r,:));
        end,tt(k,1,s==siz) = toc;

        tic;
        m = size(A,1);
        B = B(bsxfun(@plus,(ind-1)*m,(1:m).'));
        tt(k,2,s==siz) = toc;

    end
end

m = squeeze(mean(tt,1));

m(1,:)./m(2,:)

For square arrays

ans =

    0.7149    2.1508    1.2203    1.4684    1.2339    1.1855    1.0212    1.0201    0.8770       0.8584    0.8405

For twice as many columns as there are rows (same number of rows)

ans =

    0.8431    1.2874    1.3550    1.1311    0.9979    0.9921    0.8263    0.7697    0.6856    0.7004    0.7314

+1 - Impressive! I guess the JIT is pretty powerful now. I'll post results for R2008a soon. — Jacob, Apr 21 '10 at 14:42

score 6 · Answer 2 · edited Apr 21 '10 at 14:43

6

Sort() returns the index along the dimension you sorted on. You can explicitly construct indexes for the other dimensions that cause the rows to remain stable, and then use linear indexing to rearrange the whole array.

A = rand(3,4);
B = A; %// Start with same values so we can programmatically check result

[A2 ix2] = sort(A,2);
%// ix2 is the index along dimension 2, and we want dimension 1 to remain unchanged
ix1 = repmat([1:size(A,1)]', [1 size(A,2)]); %//'
%// Convert to linear index equivalent of the reordering of the sort() call
ix = sub2ind(size(A), ix1, ix2) 
%// And apply it
B2 = B(ix)
ok = isequal(A2, B2) %// confirm reordering

edited Apr 21 '10 at 14:43

Jacob

34,255
14
110
165

answered Apr 21 '10 at 13:22

Andrew Janke

23,508
5
56
85

Nice. It would be interesting to compare timing for this solution as well. – yuk Apr 21 '10 at 15:47
On the surface, it looks very similar to mine except I manually compute the linear indices and use `bsxfun`. – Jacob Apr 21 '10 at 17:22
Sad to say it's a loser performancewise. On my R2010a, this is about 25% slower than either the loop or bsxfun solution. – Andrew Janke Apr 21 '10 at 17:25
@Jacob: I think you're right, and I just had trouble reading the bsxfun() code. This doesn't seem like an improvement on OP after all. – Andrew Janke Apr 21 '10 at 17:45
@Andrew Janke: I initially wrote something very similar to your solution. Only then did I figure out the bsxfun call. That's why I wrote the loop is 'clearer' :). In general, bsxfun calls should not be allowed to exist without comments. – Jonas Apr 21 '10 at 18:07
@Jonas: I don't know really, it's very similar to using `repmat`. But yes, I agree, the loops are clearer and seem to be more efficient. – Jacob Apr 21 '10 at 18:10
2

@Jacob: `repmat` has only a single function. When I thus read `repmat`, I know what's going to happen. When I read `bsxfun`, I know that I have to really pay attention now. Having said that, it makes me happy every time I get to write `bsxfun`. bsxfun bsxfun bsxfun – Jonas Apr 21 '10 at 19:15
@Jonas: Lots of fun, isn't it :D. I used to think `bsxfun` performed the function on the rows/columns thus avoiding allocating another matrix with `repmat` but this does not seem to be true since both failed for the large matrices. – Jacob Apr 21 '10 at 19:35
@Jacob: Very interesting, thanks for sharing the observation! – Jonas Apr 21 '10 at 19:55

score 0 · Answer 3 · edited Jun 06 '12 at 05:12

0

Can't you just do this?

[val ind]=sort(A);
B=B(ind);

It worked for me, unless I'm understanding your problem wrong.

edited Jun 06 '12 at 05:12

Perception

79,279
19
185
195

answered Jun 05 '12 at 17:03

Siming

9
1

3

`ind` contains only row indices. `B = B(ind)` does not give the result required. – Alexey Nov 29 '12 at 22:17

Sort a matrix with another matrix

n = n

n = 2m

3 Answers3

Linked

Related