CODEWITHSUNDEEP
rubyarraysalgorithmsorting
Ari53nN3o
Ari53nN3o

Reputation: 1202

Sort an array according to the elements of another array

I have an array of ids 

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

and I have another array of objects with ids in random order 

a2 = [(obj_with_id_5), (obj_with_id_2), (obj_with_id_1), (obj_with_id_3), (obj_with_id_4)]

Now I need to sort a2 according to the order of ids in a1. So a2 should now become: 

[(obj_with_id_1), (id_2), (id_3), (id_4), (id_5)]

a1 might be [3, 2, 5, 4, 1] or in any order but a2 should correspond to the order of ids in a1.

I do like this: 

a1.each_with_index do |id, idx|
  found_idx = a1.find_index { |c| c.id == id }
  replace_elem = a2[found_idx]
  a2[found_idx] = a2[idx]
  a2[idx] = replace_elem
end

But this still might run into an O(n^2) time if order of elements of a2 is exactly reverse of a1. Can someone please tell me the most efficient way of sorting a2?

Upvotes: 45

Views: 20527

Answers (4)

Ajedi32
Ajedi32

Reputation: 48338

Inspired by Eric Woodruff's Answer, I came up with the following vanilla Ruby solution:

a2.group_by(&:object_id).values_at(*a1).flatten(1)

Method documentation:

Upvotes: 7

Eric Woodruff
Eric Woodruff

Reputation: 6410

I like the accepted answer, but in ActiveSupport there is index_by which makes creating the initial hash even easier. See Cleanest way to create a Hash from an Array

In fact you could do this in one line since Enumerable supports index_by as well:

a2.index_by(&:id).values_at(*a1)

Upvotes: 20

pguardiario
pguardiario

Reputation: 54984

I'll be surprised if anything is much faster than the obvious way:

a2.sort_by{|x| a1.index x.id}

Upvotes: 88

megas
megas

Reputation: 21791

hash_object = objects.each_with_object({}) do |obj, hash| 
  hash[obj.object_id] = obj
end

[1, 2, 3, 4, 5].map { |index| hash_object[index] }
#=> array of objects in id's order

I believe that the run time will be O(n)

Upvotes: 27

Related Questions