How to sort a complex vector with tie breaker angles between [0, 2π)?

By default the sort(A) function sort A by abs(A) when A is complex. If A has elements with equal magnitude, then use angle(A) in the interval (-π,π] to break ties. Therefore, we have the following sorting scheme since the first vector has the angles respectively, due to the fact angles are defined in . I want to convert the tie break angle range to , so that angles would be so that we would have the sorting scheme of .

Things I did:

• I could not find a way to provide a custom comparator function to the sort() function like it can be done in other languages like Python or C++.
• I tried the hectic way of redefining angle() function and adding new definition on top the MATLAB path. When I call the angle() function it calls my definition, but I guess since a compiled version of the built-in sort() function is called, new implementation is not used. I may be missing something here.

Of course, I can write my own mergesort or quicksort implementation with custom comparator function, but I keep thinking there must be a better way to do this.

Answer 1

[Tuna Alikasifoglu]

Based on the final solution @Jan proposed, I noticed a simple modification that can fix the problem. Since the angle() function produces angles between (-π,π], and since

angle(-1)

ans = 3.1416

which is π. By writing (-a), we basically shift the interval by π, which results in the interval (0,2π]. Hence, the real values end up with 2π angles, which are larger than every other angle. However, we want to have [0,2π) interval (or equivalently (-2π,0] interval). This can be achieved by -π shift, i.e., writing . Even though they are mathematically equivalent, we ensure that the angle is -π as:

angle(exp(-1j * pi))

ans = -3.1416

Hence, with this slight modification to the latest proposal of @Jan, we can sort a complex vector with tie breaker angles between [0,2π) as follows:

a = [0, -1j, 1j,  1,  -1, 1-1j,  1+1j, -1-1j, -1+1j, -4+3j,  3+4j];
b = [0,   1, 1j, -1, -1j, 1+1j, -1+1j, -1-1j,  1-1j,  3+4j, -4+3j];

[~, idx] = sort(exp(-1j * pi) * a);
sorted = a(idx)

sorted = 
   0.0000 + 0.0000i   1.0000 + 0.0000i   0.0000 + 1.0000i  -1.0000 + 0.0000i   0.0000 - 1.0000i   1.0000 + 1.0000i  -1.0000 + 1.0000i  -1.0000 - 1.0000i   1.0000 - 1.0000i   3.0000 + 4.0000i  -4.0000 + 3.0000i

all(sorted == b)

ans = logical
   1

Thank you @Jan and @Voss for your contribution.

[Jan]

exp(-1j * pi) is mathematically -1, but with the rounding error: -1 + 1.22e-16j . This can have side-effects for sorting large numbers.

Another idea:

aa       = [abs(a); angle(a)];
[~, idx] = sortrows(aa.');

Now mod() and adding or subtracting pi might be useful.

Answer 2

[Voss]

How about adding pi to the phase (angle) of each number, sorting, then subtracting pi again (i.e., negate, sort, negate)?

z = [2 -1 1i -1i];

sort(z) % original

ans = 
   0.0000 - 1.0000i   0.0000 + 1.0000i  -1.0000 + 0.0000i   2.0000 + 0.0000i

-sort(-z) % new

ans = 
   0.0000 + 1.0000i  -1.0000 + 0.0000i   0.0000 - 1.0000i   2.0000 + 0.0000i

[Tuna Alikasifoglu]

This is incorrect, since we expect , however your code produces .

z = [1 -1 1i -1i];
-sort(-z)

ans = 
   0.0000 + 1.0000i  -1.0000 + 0.0000i   0.0000 - 1.0000i   1.0000 + 0.0000i

Answer 3

[Jan]

Maybe it helps to sort the rotated values:

a = [2, -1, i, -i];
[~, idx] = sort(-a * 1i);
a(idx)

ans = 
   0.0000 + 1.0000i  -1.0000 + 0.0000i   0.0000 - 1.0000i   2.0000 + 0.0000i

[Tuna Alikasifoglu]

This is similar to what @Voss provided, but instead of shifting by π, you are shifting with . This is also incorrect, since we expect due to the fact that first vector have the angles . However, your code produces :

a = [1-1i, 1+1j, -1-1i, -1+1i];
[~, idx] = sort(-a * 1i);
a(idx)

ans = 
   1.0000 - 1.0000i   1.0000 + 1.0000i  -1.0000 + 1.0000i  -1.0000 - 1.0000i

[Jan]

"since we expect" - I do not think that I really know, what you expect. But I assume you can understand the idea of modifying the data by rotating them instead of inventing a new sorting function.

Unfortunately you have provided a not exhaustive set of inputs in a format, which cannot be used by copy&paste. This makes it tedious to modify the suggested method until it matchs your expectations. But maybe you can adjust this idea to your needs?

What about:

a = [1-1i, 1+1j, -1-1i, -1+1i];
[~, idx] = sort(-a);
a(idx)

ans = 
   1.0000 + 1.0000i  -1.0000 + 1.0000i  -1.0000 - 1.0000i   1.0000 - 1.0000i

[Tuna Alikasifoglu]

Maybe I could not express myself very clear, let me try again. MATLAB sorts complex vectors with following strategy: Sort A by abs(A) when A is real or complex. If A has elements with equal magnitude, then use angle(A) in the interval (-π,π] to break ties. I want to break ties with the interval [0,2π). I provided a simple example to showcase a basic end result. Then, you and @Voss provided solutions that generate the correct output for the given case. However, these solutions do not achieve what I described for all cases, so I provided counter examples such that your snippets fail to generate correct output. Finally, the final solution you provided is correct for the given case but fails again for 0 imaginary part (real) elements. However, this gave me an idea why these may fail, I will post the solution if it works. Meanwhile I provided an exhaustive input a with the expected sorted version of b, as you can see they do not match.

a = [0, -1j, 1j,  1,  -1, 1-1j,  1+1j, -1-1j, -1+1j, -4+3j,  3+4j];
b = [0,   1, 1j, -1, -1j, 1+1j, -1+1j, -1-1j,  1-1j,  3+4j, -4+3j];

[~, idx] = sort(-a);
sorted = a(idx)

sorted = 
   0.0000 + 0.0000i   0.0000 + 1.0000i  -1.0000 + 0.0000i   0.0000 - 1.0000i   1.0000 + 0.0000i   1.0000 + 1.0000i  -1.0000 + 1.0000i  -1.0000 - 1.0000i   1.0000 - 1.0000i   3.0000 + 4.0000i  -4.0000 + 3.0000i

all(sorted == b)

ans = logical
   0