Efficient sorting of 2 Vectors with many duplicate values?

General Usage
,
1

I have two vectors, X, Y that represent positions of 2D points. Both of these vectors have a lot of duplicates, but there is no duplicate point (i.e. many points have same x or y coords, but no points have both x and y the same).

I am trying to sort these vectors such that they are first sorted by increasing X and then by increasing Y. Is there a straight-forward way to do it?

My current approach is to first sort X. Then, for each section of X that has the same value, sort the corresponding section of Y. Get these sorting indices (with sortperm) and put their values in the master sorting vector. Continue until the end.

This seems kinda bad though :stuck_out_tongue:

2

You could represent your points as tuples:

julia> sort([(3,4), (3,2)])                                                                                                                           
2-element Array{Tuple{Int64,Int64},1}:                                                                                                                
 (3, 2)                                                                                                                                               
 (3, 4)

Or use Point from GitHub - JuliaGeometry/GeometryTypes.jl: Geometry types for Julia, which I suspect would allow similar sorting. (Edit: Iā€™m not sure Point actually exists, but something along those lines.)

1 Like
3

Holy bananas it was that simple? Really? Damnit.

Yeap, using sortperm(collect(zip(X,Y))) does exactly what I need! and it is suprisingly fast as well!
14ms for Vectors with 30,000 elements.

3 Likes