CODEWITHSUNDEEP
rubysorting
TIMBERings
TIMBERings

Reputation: 768

Ruby - Why does sort reorder equal elements

I'm trying to reverse sort an array of hashes without changing the order of hashes that are equal. However I am not seeing this functionality with sort.

For example,

[{a:1, b:2}, {a:0, b:5}, {a:1,b:4}, {a:1,b:3}].sort { |a,b| b[:a] <=> a[:a] }
# actual:   [{:a=>1, :b=>2}, {:a=>1, :b=>3}, {:a=>1, :b=>4}, {:a=>0, :b=>5}]
# expected: [{:a=>1, :b=>2}, {:a=>1, :b=>4}, {:a=>1, :b=>3}, {:a=>0, :b=>5}]

The hashes with :b=>4 and :b=>3 are incorrectly re-ordered. Am I misinterpreting how sort works?

Upvotes: 3

Views: 715

Answers (2)

Ben
Ben

Reputation: 9895

It looks you have issue with the fact that it reordered some of the entries in the array that had a matching value. This is because of the quicksort algorithm used by the native ruby sort.

You read about quicksort here http://en.wikipedia.org/wiki/Quicksort and an article about ruby implentation here https://www.igvita.com/2009/03/26/ruby-algorithms-sorting-trie-heaps.

The result you get is sorted properly based on the sort criteria, but it may reorder some of the similar entries in the process.

Upvotes: 2

Max
Max

Reputation: 22325

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

Upvotes: 5

Related Questions