user1934428 user1934428 -4 years ago 56
Ruby Question

Stable #sort taking a block

We find here an implementation of a stable sort_by in Ruby, which works for the general case (i.e. I can supply my own comparision algorithm), and in this thread user tokland describes a very elegant way to do a stable sort_by:

module Enumerable
def stable_sort_by
sort_by.with_index { |x, idx| [yield(x), idx] }
end
end


The idea of using an Enumerator object together with with_index is surprisingly simple! I would like to find a similar elegant solution to create a stable version of the #sort function where it is given a comparison block. It would be used like this:

sorted_people = people.stable_sort do |person|
person.name
end

Answer Source

Here's a solution (but far from elegant):

module Enumerable
  def stable_sort
    each_with_index.sort { |(x, i), (y, j)|
      r = yield(x, y)
      r == 0 ? i <=> j : r
    }.map(&:first)
  end
end

It generates an array of [element, index] pairs and sorts them by passing each two elements to the given block (just like sort does). If the block returns 0, it compares the indices, otherwise, it returns the block's result. Afterwards, the elements are extracted from the generated array.

Example:

arr = [[2, :baz], [1,:foo], [1, :bar]]

arr.sort { |x, y| x[0] <=> y[0] }
#=> [[1, :bar], [1, :foo], [2, :baz]]

arr.stable_sort { |x, y| x[0] <=> y[0] }
#=> [[1, :foo], [1, :bar], [2, :baz]]
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download