Is Sort in Ruby Stable

Is sort in Ruby stable?

Both MRI's sort and sort_by are unstable. Some time ago there was a request to make them stable, but it was rejected. The reason: Ruby uses an in-place quicksort algorithm, which performs better if stability is not required. Note that you can still implement stable methods from unstable ones:

module Enumerable
  def stable_sort
    sort_by.with_index { |x, idx| [x, idx] }
  end

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

Ruby sort_by keep original order of not sorted

You can make sort_by stable by incorporating with_index.

Instead of:

collection.sort_by { |...| ... }

You write:

collection.sort_by.with_index { |(...), i| [..., i] }

Applied to your problem:

hash.sort_by { |_k, v| v['top'] ? 0 : 1 }                      # unstable

hash.sort_by.with_index { |(_k, v), i| [v['top'] ? 0 : 1, i] } # stable

How do I do stable sort?

Put the key that you originally wanted to sort by and the index into an array, and sort by that.

a.sort_by.with_index { |(x, y), i| [y, i] }
  # => [[:a, 0], [:c, 0], [:d, 0], [:b, 1]]

What does it mean (and imply) that quicksort in Ruby is not stable?

Non stability isn’t that the sort will give different results with the same input list. It’s that when you sort an input list by some order, elements that are equivalent according to the order are not guaranteed to be in the same positions relative to each other in the output as the input.

Say, sorting a line of people by increasing integer age. For people of the same age in the line, there isn’t a way to pick who should be first, second etc: they are equivalent. A stable sort’s output would preserve their relative positions as they were in in the input line. Say, Alice and Bob are both 43, and Bob was ahead of Alice in the original line. A stable sort guarantees that Bob would be ahead of Alice in the output line. An unstable sort would not.

The comment of “unpredictable” is slightly misleading. Given enough information about the algorithm, or how it behaved with the same input, it is predictable. However, if all you know is that it’s an unstable sort, it’s not. Specifically, how equivalent elements are sorted is not predictable.

Stable #sort taking a block

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]]

Ruby 2.3.1 sort_by function change?

Ruby doesn't guarantee you a sort order if the items are the same.

As to why the result changed between versions, this looks like a relevant change: ruby 2.3 tries to use a c-standard library provided implementation of quicksort in more cases than before.

Which algorithm does Ruby's sort method use?

Look here: http://www.igvita.com/2009/03/26/ruby-algorithms-sorting-trie-heaps/

It does natively use quicksort however, which is n log n complexity on average.

Ruby - Why does sort reorder equal elements

Array#sort uses a quicksort algorithm under the hood. This algorithm is not stable: there is no guarantee that equal elements will not be reordered in the output. Basically when you sort in Ruby, you should specify exactly how things should be sorted rather than leave it up to chance. You can handle your case by using sort_by and adding the element's index to the sorting criteria:

ary.sort_by.with_index { |h, i| [-h[:a], i] }

---

Related Topics