Geek asks and answers

Sort an array of numbers based on a given order

I have two arrays. The first array contains the sort order. The second array contains an arbitrary number of elements.

I have the property that all elements (by value) from the second array are guaranteed to be in the first array, and I only work with numbers.

A = [1,3,4,4,4,5,2,1,1,1,3,3]
Order = [3,1,2,4,5]

When I sort A, I would like the elements to appear in the order specified Order:

[3, 3, 3, 1, 1, 1, 1, 2, 4, 4, 4, 5]

Please note that duplicates are fair play. Elements in should not be changed, only reordered. How can i do this?

+5
source share
3 answers
>> source = [1,3,4,4,4,5,2,1,1,1,3,3]
=> [1, 3, 4, 4, 4, 5, 2, 1, 1, 1, 3, 3]
>> target = [3,1,2,4,5]
=> [3, 1, 2, 4, 5]
>> source.sort_by { |i| target.index(i) }
=> [3, 3, 3, 1, 1, 1, 1, 2, 4, 4, 4, 5]
+11
source

If (and only if!) @Gareth the answer is too slow, use:

# Pre-create a hash mapping value to index once only…
index = Hash[ Order.map.with_index.to_a ] #=> {3=>0,1=>1,2=>2,4=>3,5=>4}

# …and then sort using this constant-lookup-time
sorted = A.sort_by{ |o| index[o] }

tested:

require 'benchmark'

order = (1..50).to_a.shuffle
items = 1000.times.map{ order.sample }
index = Hash[ order.map.with_index.to_a ]

Benchmark.bmbm do |x|
  N = 10_000
  x.report("Array#index"){ N.times{
    items.sort_by{ |n| order.index(n) }
  }}
  x.report("Premade Hash"){ N.times{
    items.sort_by{ |n| index[n] }
  }}
  x.report("Hash on Demand"){ N.times{
    index = Hash[ order.map.with_index.to_a ]
    items.sort_by{ |n| index[n] }
  }}
end

#=>                      user     system      total        real
#=> Array#index     12.690000   0.010000  12.700000 ( 12.704664)
#=> Premade Hash     4.140000   0.000000   4.140000 (  4.141629)
#=> Hash on Demand   4.320000   0.000000   4.320000 (  4.323060)
+4
source

Another possible solution without explicit sorting:

source = [1,3,4,4,4,5,2,1,1,1,3,3]
target = [3,1,2,4,5]
source.group_by(&lambda{ |x| x }).values_at(*target).flatten(1)
+1
source

More articles:


All Articles