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

Ruby
1

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 }

2

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.

3

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

4

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.