Loren on the Art of MATLAB

Reversal of a sort 24

Posted by Loren Shure,

We can sometimes be motivated to reverse things in Boston. And I occasionally get asked how to reverse the sort direction from MATLAB. So instead of sorting A and then having B follow the new order, let's undo a sorting operation, and in a way that multiple vectors could benefit, if necessary.

Contents

Forward Sorting

To sort multiple additional vectors in the same way as an initial one, we can easily take advantage of the sort index.

A = [1 8 3 17 0 4 7];
[sortA, ind] = sort(A);
B = [2 5 6 1 9 3 8];
sortBbyA = B(ind);
sortB = sort(B);

Here are the indices required to rearrange A into sortA.

ind
ind =
     5     1     3     6     7     2     4

And here's a comparison of the original vectors and the ones sorted by the order in A.

[A;B]
[sortA;sortBbyA]
ans =
     1     8     3    17     0     4     7
     2     5     6     1     9     3     8
ans =
     0     1     3     4     7     8    17
     9     2     6     3     8     5     1

You can see that each number in A still corresponds to the same value from B after each vector has been sorted based on A.

Now let's have a look at the variants of the vector B.

[B;sortB;sortBbyA]
ans =
     2     5     6     1     9     3     8
     1     2     3     5     6     8     9
     9     2     6     3     8     5     1

You can see that sorting B according to A (the 3rd row) is distinct from sorting B directly (second row).

Reverse Sorting

Suppose instead, I want all my vectors to be sorted the same way that the original A is sorted. I can still use the index from sort but in a different way.

unsorted = 1:length(A);
newInd(ind) = unsorted
newInd =
     2     6     3     7     1     4     5

We are now in a position to undo the original sorting of A and apply the rearrange variants of B the same way. First we'll work with the variant of B based on sorting from A.

newA = sortA(newInd);
newBfromA = sortBbyA(newInd);
isequal([newA;newBfromA],[A;B])
ans =
     1

Now let's compare several variants: B, the regular sorting of B, B sorted by A, and the sorted B rearranged according to the reverse sorting of A

newB = sortB(newInd);
[B;sortB;sortBbyA;newB]
ans =
     2     5     6     1     9     3     8
     1     2     3     5     6     8     9
     9     2     6     3     8     5     1
     2     8     3     9     1     5     6

Help Me Here

Now I've shown how to use the direct sorting indices of a vector to reverse sort another vector. I can even vaguely recall needing to do this once, but I can no longer remember why. Do you use this construct? Can you tell me some applications? I'd love to hear about them; please post here.


Get the MATLAB code

Published with MATLAB® 7.5

24 CommentsOldest to Newest

I often use this idea that you call “reverse sorting”, for inverse permutation vectors and matrices (did I say “inverse”?? Yes, I did).

For a permutation matrix, P, the inverse is P’. (P transpose). However, many functions such as sort, amd, randperm, and the like return permutation vectors, not permutation matrices. Transposing a permutation *matrix* gives the “reverse” or “inverse” permutation matrix, but that doesn’t work for a permutation vector. Sometimes I need to compute P’*A where I have P not as a matrix but a permutation vector. In that case, I need to do what you call “reverse sorting”.

For example, try this code, an example of what you call “reverse sorting”:

rand (‘state’,0) ;
A = rand (5)
[ignore p] = sort (A (:,1)) ;
p
B = A (p,:)
n = length (p) ;
pinv (p) = 1:n
C = B (pinv,:)
A-C

The matrices A and C are equal.

The permutation vector p is “inverted”, giving pinv. Then permuting A once gives B, permuting B back via pinv gives C which is now equal to A. Here is a matrix interpretation of what just happened above.

P = sparse(1:n,p,1) ;
B – P*A
C – P’*B

So reversing a sort is just like inverting a matrix … well, a very special matrix that’s easy and accurate to invert by just transposing it. Permutation matrices are special cases of orthogonal matrices.

You can go back and forth between permutation vectors and matrices with these statements:

[p j x] = find(P’), convert row permutation P*A to A(p,:)

[q j x] = find(Q), convert column permutation A*Q to A(:,q)

P=sparse(1:n, p, 1), convert row permutation A(p,:) to P*A

Q=sparse(q, 1:n, 1), convert column permutation A(:,q) to A*Q

Loren writes “We can sometimes be motivated to reverse things in Boston.” It’s actually harder to reverse things in Natick that it is in Boston itself. Ever try making a U-turn on Route 9?

Tim—You’re right, of course. Many of the MathWorkers here have to reverse direction on Route 9 every day, and it is good for neither the mood nor the blood pressure. :-)

It’s not quite the same implementation, but I’ve found reverse sorting useful in “undoing” a permutation. Typically, I would generate a list of stimuli for an experiment and permute the sequence for the actual presentation. When analyzing the data (one response for each stimulus), I need to undo the permutation and recover the original (sorted) sequence.

———
seq = 1:N;
idx = randperm(N);
scrambledList = seq(idx);

% experiment yields scrambledResponses

[ignore reverseIdx] = sort(idx);
sortedResponses = scrambledResponses(reverseIdx);
——-

Oh my, someone was in a good mood when they wrote this, the puns are just everywhere.

Unfortunately, I don’t have much else to add to the discussion because everything I do is always a measurement in space or time, and then there is sort of a natural order to things already. No sorting required.

If one is dealing with filter coefficients, and needs to store the even and odd filter coefficients separately, but then needs to restore the coefficients to their original order later, this “reverse” sorting could be made useful. I’ll be rewriting some code…

A reversal of a sort occurs in LU factorization. With 4 outputs, LU returns row and column permutations p and q. To compute x, you need to undo the “sort” that LU did on the columns of A. That is, L*U equals A(p,q), and to solve Ax=b you do the following:

load west0479
A = west0479 ;
n = size(A,1) ;
b = rand (n,1) ;
[L,U,p,q] = lu (A, ‘vector’) ;
norm (L*U – A(p,q),1) / norm (A,1)
x = U\(L\b(p)) ;
x (q) = x ;
norm (A*x-b)

The statement x(q)=x undoes the column permutation of A.

Daniel: The “sort” done by pivoting in dense or sparse LU occurs for any matrix … including those arising from discretizations of space and/or time. So if you use x=A\b then you’ve got a kind of sort going on already, even though you have a “natural order”. Note, for example, that the “natural” order for a 2D mesh is not at all the best ordering to use for the factorization. It’s actually pretty bad in terms of work and fill-in (memory usage). So sometimes, the “natural” thing is not the best thing.

I just wanted to thank you for showing the reverse sorting. I had this problem in my HW and tried all day to figure it out.

Thank You!

Sometimes I need to find the max N elements in a matrix M. It would be nice if “find” can be extended to support find(M, N, “min”) and find(M, N, “max”) which would find the smallest N and largest N elements. In the standard C++ STL library there is a partial sort algorithm which makes it more efficient than sorting the entire matrix.

help me in this please
x=1:10
[temp, alpha] = sort(rand(1,10));
seq=x(alpha);

from ‘seq’ how do i get back ‘x’

Arun-

Here’s one way.

xx = 1:length(alpha);
xxMixed = xx(alpha);
[xresort, indresort] = sort(xxMixed);
xrestored = seq(indresort);
isequal(xrestored, x)

The idea is to get the original length of x, mix it up the same way (by indexing with alpha). Sort that new array back, getting indices and using those to unscramble seq.

–Loren

i sometimes want to sort just the first m elements of an n dimensional vector. is there a fast way of doing this?

Joshua-

The way I can think of is to first extract the first M elements and then sort them.

–Loren

Just wondering if I have two vectors, one is the permuted of the other, for example, in your case,
[1 8 3 17 0 4 7]
and
[0 1 3 4 7 8 17]
How can I conveniently find the permutation
[5 1 3 6 7 2 4]?

Many thanks.

Qiang-

Fun question, easy answer if you know what function to use:

a = [1 8 3 17 0 4 7]
b = [0 1 3 4 7 8 17]
[~,ind] = ismember(b,a)

% the output
>> a = [1 8 3 17 0 4 7]
a =
     1     8     3    17     0     4     7
>> b = [0 1 3 4 7 8 17]
b =
     0     1     3     4     7     8    17
>> [~,ind] = ismember(b,a)
ind =
     5     1     3     6     7     2     4

–Loren

this is quite often used in actuarial science to induce dependence into a sample which is uncorrelated a priori.

see the document
Correlation and aggregate loss distributions with an emphasis on the Iman-Conover Method. Mildenhall, S.J. 2005

Qiang,

Here is one solution:

function idx = USearch(p,v);
% 
% Un-Ordered Search for idx : v = p(idx).
% Complexity: O(n);
% USE: for i = 1:7,p(i) = USearch(a,b(i)); end;
% Derek O'Connor, 31 Jan 2011.
%
n = length(p);
idx=0;
for k = 1:n
    if p(k) == v
        idx=k;
        return;             % stops after first find.
    end;
end;
return; % USearch

Use this function as follows:

>> for i = 1:7,p(i)=USearch(a,b(i)); end; disp(p)
     5     1     3     6     7     2     4

Unfortunately this method of finding p(1:n) is O(n^2).

Homework Assignment (Due 7 Jan 2011): Find a quicker method.

Good luck, Derek O’Connor.

Can reverse sort work with a matrix where each column has been sorted?

I am trying to do the following:

let’s say i have a matrix ‘A’ of 7000 rows by 50 columns, and i sort using the following:

[sortA, ind] = sort(A,'descend');

now I export this matrix as a .txt file and replace all of the values in Excel with different ones. Then import the altered matrix back into matlab as ‘B’. Therefore ‘B’ has the same dimensions as A but the values have been altered. How can i apply the reverse sort (‘SortA’ to ‘A’) to matrix ‘B’?
Thanks in advance.

Mike B-

There is an example in the help to show how to undo the sort. You need to save the indices from the initial sort and use those with the new data.

–Loren

when i need to sort a matrix here what i do

[m,n] = size(X);
newX = reshape(X,1,m*n);

then use the same thing as loren did with A & B vector

then again reshape my sorted vector back to matrix

this way of sorting is equal to sorting by column then sorting the rows

but if u need to sort only the columns or rows of matrix i dunno how to do it

Thanks for the entry! it was very useful. I was struggling in how to assign each pixel in a matrix its rank. I guessed it has to do with sort, but the inverse sort was actually what I was after.

I’m trying to find local maxima in an image. Converting to probabilities (rank/numel) and running a local product (colfilt(img,[3 3],’sliding’,@prod)) worked really great,

Roy

Roy—Since you’re calling colfilt, you must have Image Processing Toolbox, so I suggest that you call imdilate in order to find local maxima in an image.

These postings are the author's and don't necessarily represent the opinions of MathWorks.