CODEWITHSUNDEEP
ruby-on-railsruby
dev_054
dev_054

Reputation: 3748

Ruby - Implementing custom sort

I have this array of Hash:

hash =    
[
  {
    distance: 0.3997651063189804, project_id: 1, project_name: "Project 1", project_dependents_ids: [4]
  },
  {
    distance: 0.414026818885287, project_id: 2, project_name: "Project 2", project_dependents_ids: [1]
  },
  {
    distance: 0.6259577862775509, project_id: 3, project_name: "Project 3", project_dependents_ids: []
  },
  {
    distance: 0.43719371056189227, project_id: 4, project_name: "Project 4", project_dependents_ids: [3]
  },
  {
    distance: 0.4341702282185951, project_id: 5, project_name: "Project 5", project_dependents_ids: []
  }
]

I have to sort it by distance first, BUT, if the project has project_dependents (self association), it must comes after the project associated.

Ex:

A simple sort by distances, as below:

hash.sort! { |a, b| b[:distance] <=> a[:distance] }

... will result in:

But this result isn't 100% what I want. I want to sort it also by the project_dependents. Ex:

The result must be:

It's just a simple example. A project can have many self association ids and so on..

So, I want to know how I can implement this kind of sort. Maybe a general idea would be helpful. All the implementations that I made here got giant code and incorrect result.

Upvotes: 2

Views: 267

Answers (1)

Amadan
Amadan

Reputation: 198496

Without the distance requirement, Ruby's TSort is exactly the tool for the job. However, I couldn't figure out how to add an extra requirement to the topological sort, so...

One idea is to start with a sorted array, then rearrange it by pushing each element just past all of its dependents. E.g. Starting with the sorted order

[3, 4, 5, 2, 1]

we leave 3 alone (no dependents), leave 4 alone (all its dependents are left of it), leave 5 alone (no dependents), push 2 after 1 (because 1 is its dependent and to its right), then leave 1 alone (all its dependents are left of it), and leave 2 alone (all its dependents are left of it).

This will result in an infinite loop if you have circular dependencies. It can be defended against, but I'll leave it as an exercise to the reader :) (E.g. you could keep a Set of all nodes pushed at curr, and clear it when curr is incremented; if you try to re-push the same one, raise an error)

array = hash # because your naming makes no sense :)
hash = array.each.with_object({}) { |o, h| h[o[:project_id]] = o }

order = array.map { |o| o[:project_id] }.sort_by { |id| -hash[id][:distance] }

order.each_index do |curr|
  dependents = hash[order[curr]][:project_dependents_ids]
  max_dep_index = dependents.map { |d| order.index(d) }.max
  if max_dep_index&.> curr
    order[curr .. max_dep_index - 1], order[max_dep_index] =
      order[curr + 1 .. max_dep_index], order[curr]
    redo
  end
end

result = hash.values_at(*order)

EDIT: This is not terribly efficient, all those .index calls, and I have this feeling it should be possible to do it better...

EDIT2: Made the loop more Rubyish.

Upvotes: 3

Related Questions