Ruby - Implementing custom sort

Question

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:

Project 3
Project 4
Project 5
Project 2
Project 1

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

The result must be:

Project 3
Project 4
Project 5
Project 1 # Project 1 has less distance, BUT project 2 depends of it.
Project 2

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.

If this is data from your database, this is almost certainly something you should be doing in your ActiveRecord query (order), not with sort. — Jordan Running
– Jordan Running, Commented Feb 8, 2017 at 3:11
Unfortunately this data isn't coming from my database. This is the result of some math calculations that I did in my controller. I just got stucked with this, it's a bit complex. — dev_054
– dev_054, Commented Feb 8, 2017 at 3:12
1.In your example, the values of :project_dependents_ids are empty arrays or arrays containing a single dependent id. The name of the key suggests those arrays may contain more than one dependent id. Can they? 2. Can the ids be such that 2 must follow 1, 3 must follow 2 and 1 must follow 3 (in which case that impossibility would have to be identified in code)? This is not an easy problem. — Cary Swoveland
– Cary Swoveland, Commented Feb 8, 2017 at 4:18
@CarySwoveland: 1. Yes, :project_dependents_ids can contain more than one dependent. 2. Well, it's a problem (a circular dependence) that I've already solved (or I think I've solved) before do this kind of sort. Yes, I know it isn't an easy problem, that's why I'm stucked :( — dev_054
– dev_054, Commented Feb 8, 2017 at 4:19

Amadan · Accepted Answer · 2017-02-08 05:58:08Z

3

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.

edited Feb 8, 2017 at 5:58

answered Feb 8, 2017 at 4:29

Amadan

200k23 gold badges253 silver badges321 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

dev_054 Over a year ago

Awesome! I just tested your code here and it really works, different than mine (which currently is a complete mess). Thanks for your answer, it helped me a lot. Now I'll study your code ^^. By the way, I took a look in Tsort module and it's so great, I've never heard about it before.. too bad that it doesn't fit in my case.

dev_054 Over a year ago

Hello @Amadan, I was thinking about TSort.. and I think it can fit in my case if I just sort the items by distance first and then call .tsort. Or is there something that I'm missing?

Amadan Over a year ago

Oh, nice. I tried sorting the each_child order, but didn't try that. Cheers.

Collectives™ on Stack Overflow

Ruby - Implementing custom sort

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related