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
Executing Code For Every Method Call in a Ruby Module
Tzinfo::Datasourcenotfound Error Starting Rails V4.1.0 Server on Windows
Converting a Nested Hash into a Flat Hash
How to Validate a Date in Rails
String Concatenation Vs. Interpolation in Ruby
Difference Between Various Variables Scopes in Ruby
In Ruby on Rails, to Extend the String Class, Where Should the Code Be Put In
How to Get Argument Names Using Reflection
Using Sinatra For Larger Projects Via Multiple Files
Reducing N+1 Queries Using the Bullet and Rspec Gems
What Does @@Variable Mean in Ruby
How Does Instance_Eval Work and Why Does Dhh Hate It