# How can I do the below operation less then O(n2) time?

arr = [
{:id=>12, :name=>“foo1”}, {:id=>15, :name=>“foo3”},
{:id=>26, :name=>“foo2”}, {:id=>18, :name=>“foo4”}
]

sort_order = [15,12,18,26]

# below is working, but O(n2)

sort_order.map { |id| arr.find { |h| h[:id] == id }

On Fri, Mar 14, 2014 at 3:35 PM, Arup R. [email protected]
wrote:

arr = [
{:id=>12, :name=>“foo1”}, {:id=>15, :name=>“foo3”},
{:id=>26, :name=>“foo2”}, {:id=>18, :name=>“foo4”}
]

sort_order = [15,12,18,26]

# below is working, but O(n2)

sort_order.map { |id| arr.find { |h| h[:id] == id }

My solution builds an index first in a hash, O(n), followed by a
sort_by the indexed value. Checking the index is O(1), and sort_by I
suppose it’s O(n*log n) (can someone confirm which is the time
complexity of sort_by?)

2.0.0p195 :011 > index = {}
=> {}
2.0.0p195 :012 > sort_order.each_with_index {|e,i| index[e] = i}
=> [15, 12, 18, 26]
2.0.0p195 :013 > arr.sort_by {|h| index[h[:id]]}
=> [{:id=>15, :name=>“foo3”}, {:id=>12, :name=>“foo1”}, {:id=>18,
:name=>“foo4”}, {:id=>26, :name=>“foo2”}]

So, that should make it O(n*log n), or whatever the complexity of
sort_by is.

Hope this helps,

Jesus.

On Fri, 14 Mar 2014 15:35:49 +0100
Arup R. [email protected] wrote:

arr = [
{:id=>12, :name=>“foo1”}, {:id=>15, :name=>“foo3”},
{:id=>26, :name=>“foo2”}, {:id=>18, :name=>“foo4”}
]

sort_order = [15,12,18,26]

# below is working, but O(n2)

sort_order.map { |id| arr.find { |h| h[:id] == id }

You can also use sort_order directly

``````arr.sort_by{|i| sort_order.index(i[:id]) }
``````

Note that `sort_order.index` will be called only once for each `arr`
entry

On Fri, Mar 14, 2014 at 5:54 PM, Sergey Avseyev
[email protected] wrote:

# below is working, but O(n2)

sort_order.map { |id| arr.find { |h| h[:id] == id }

You can also use sort_order directly

``````arr.sort_by{|i| sort_order.index(i[:id]) }
``````

Note that `sort_order.index` will be called only once for each `arr`
entry

Please note that this is O(n2) still. Calling index once for each
element in arr, makes it O(n) calls, and the index method itself is
also linear, so O(n) * O(n).

Jesus.