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
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!