Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 710
Ari53nN3o Avatar asked Aug 14 '12 22:08

Ari53nN3o


People also ask

How do you sort an array in ascending order based on the ranks of each element which is in the another array?

The short answer is: std::sort . The basic idea is to create a std::vector<std::pair<int,int>> and then simply sort that via std::sort . The rest of the code is about copying the values and ranks into that vector and copying the values out of it after sorting.

How do you sort an array in a specific order?

Sorting an array of objects in javascript is simple enough using the default sort() function for all arrays: const arr = [ { name: "Nina" }, { name: "Andre" }, { name: "Graham" } ]; const sortedArr = arr.


3 Answers

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

a2.sort_by{|x| a1.index x.id}
like image 128
pguardiario Avatar answered Oct 17 '22 13:10

pguardiario


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)

like image 27
megas Avatar answered Oct 17 '22 12:10

megas


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)
like image 20
Eric Woodruff Avatar answered Oct 17 '22 11:10

Eric Woodruff