How to sort two or more lists at once?

General Usage
, ,
13

This is a bit old, but let me just point out that Julia beautifully allows one to solve this problem by defining a custom type that holds a number of arrays, and teaching it how to sort itself. Then sort! can sort using the values in the first array, but updating the order for the second array too. This allows a solution that is faster, and with less allocations, than the sortperm approach. But of course it requires quite a bit more code

struct CoSorterElement{T1,T2}
    x::T1
    y::T2
end
struct CoSorter{T1,T2,S<:AbstractArray{T1},C<:AbstractArray{T2}} <: AbstractVector{CoSorterElement{T1,T2}}
    sortarray::S
    coarray::C
end

Base.size(c::CoSorter) = size(c.sortarray)
Base.getindex(c::CoSorter, i...) = 
    CoSorterElement(getindex(c.sortarray, i...), getindex(c.coarray, i...))
Base.setindex!(c::CoSorter, t::CoSorterElement, i...) = 
    (setindex!(c.sortarray, t.x, i...); setindex!(c.coarray, t.y, i...); c) 
Base.isless(a::CoSorterElement, b::CoSorterElement) = isless(a.x, b.x)
Base.Sort.defalg(v::C) where {T<:Union{Number, Missing}, C<:CoSorter{T}} = 
    Base.DEFAULT_UNSTABLE

With this you can do

julia> cur_x = rand(1:10, 10); cur_y = rand(10); using BenchmarkTools

julia> c = CoSorter(cur_x, cur_y); @btime sort!($c)
  30.111 ns (0 allocations: 0 bytes)
10-element CoSorter{Int64,Float64,Array{Int64,1},Array{Float64,1}}:
 CoSorterElement{Int64,Float64}(1, 0.40265954276014937)  
 CoSorterElement{Int64,Float64}(3, 0.07364824869474873)  
 CoSorterElement{Int64,Float64}(4, 0.7341851985737331)   
 CoSorterElement{Int64,Float64}(5, 0.0010439543093452297)
 CoSorterElement{Int64,Float64}(6, 0.8187812476982932)   
 CoSorterElement{Int64,Float64}(6, 0.8235149239112314)   
 CoSorterElement{Int64,Float64}(7, 0.891985683971432)    
 CoSorterElement{Int64,Float64}(7, 0.5556465187657322)   
 CoSorterElement{Int64,Float64}(8, 0.9217791949844834)   
 CoSorterElement{Int64,Float64}(10, 0.32895616976956177)

The original arrays have now been co-sorted in-place.

For comparison, I think the next fastest is @anon94023334’s solution

julia> @btime sort(collect(zip($cur_x, $cur_y)); by=first);
  111.781 ns (5 allocations: 608 bytes)

EDIT: some corrections

6 Likes