CODEWITHSUNDEEP
rubyarrayssorting
Chloe
Chloe

Reputation: 26264

My Ruby array is sorted non-deterministicly

When I sort this array, it keeps returning different sort orders.

a = [ [0, 'cow'], [0, 'chicken'], [0, 'cat'], [0, 'goat'], [0, 'sheep'], [0, 'pig']]
a.push [1, 'dog']

a.sort_by! { |s| s[0] }
# => [[0, "cow"], [0, "chicken"], [0, "cat"], [0, "pig"], [0, "sheep"], [0, "goat"], [1, "dog"]]
a.sort_by! { |s| s[0] }
# => [[0, "cow"], [0, "chicken"], [0, "cat"], [0, "goat"], [0, "sheep"], [0, "pig"], [1, "dog"]]
a.sort_by! { |s| s[0] }
# => [[0, "cow"], [0, "chicken"], [0, "cat"], [0, "pig"], [0, "sheep"], [0, "goat"], [1, "dog"]]
a.sort_by! { |s| s[0] }
# => [[0, "cow"], [0, "chicken"], [0, "cat"], [0, "goat"], [0, "sheep"], [0, "pig"], [1, "dog"]]
a.sort_by! { |s| s[0] }

Why am I getting different sort orders?

Upvotes: 0

Views: 300

Answers (3)

Abdo
Abdo

Reputation: 14051

When you do two sort_by! followed by each other, you should be aware that you're not feeding the same input to the first method as the second methods since sort_by! is modifying a before you feed it into the second sort_by!

a = [ [0, 'cow'], [0, 'chicken'], [0, 'cat'], [0, 'goat'], [0, 'sheep'], [0, 'pig'], [1, 'dog']]

a.sort_by! { |s| s[0] }

=> [[0, "cow"],
 [0, "chicken"],
 [0, "cat"],
 [0, "pig"],
 [0, "sheep"],
 [0, "goat"],
 [1, "dog"]]

a becomes this last array. Now when you sort the second time, you're feeding a different input.

Now, in order to confirm that the algorithm is deterministic, do this:

sorted = []; 100.times { a = [ [0, 'cow'], [0, 'chicken'], [0, 'cat'], [0, 'goat'], [0, 'sheep'], [0, 'pig'], [1, 'dog']]; sorted << a.sort_by! { |s| s[0] } }

sorted.uniq.count
=> 1

Upvotes: 2

Patrick Oscity
Patrick Oscity

Reputation: 54684

Ruby uses Quicksort, which is an unstable sorting algorithm. This means that the order of equal elements may change after the array is sorted.

Now if you use sort_by instead of the mutator method sort_by!, the array you started with will not be altered. Therefore, sort_by will yield the same result every time.

When you use sort_by!, the original array is replaced with the sorted one and thus the elements may change their order after each iteration. This means the output isn't nondeterministic, it just depends on the input.

Upvotes: 2

Chloe
Chloe

Reputation: 26264

Use a = a.sort_by instead. #sort_by! appears to be non-deterministic.

irb(main):132:0> a.sort_by { |s| s[0] }
=> [[0, "cow"], [0, "chicken"], [0, "cat"], [0, "pig"], [0, "sheep"], [0, "goat"], [1, "dog"]]
irb(main):133:0> a.sort_by { |s| s[0] }
=> [[0, "cow"], [0, "chicken"], [0, "cat"], [0, "pig"], [0, "sheep"], [0, "goat"], [1, "dog"]]
irb(main):134:0> a.sort_by { |s| s[0] }
=> [[0, "cow"], [0, "chicken"], [0, "cat"], [0, "pig"], [0, "sheep"], [0, "goat"], [1, "dog"]]
irb(main):135:0> a.sort_by { |s| s[0] }
=> [[0, "cow"], [0, "chicken"], [0, "cat"], [0, "pig"], [0, "sheep"], [0, "goat"], [1, "dog"]]
irb(main):136:0> a.sort_by { |s| s[0] }
=> [[0, "cow"], [0, "chicken"], [0, "cat"], [0, "pig"], [0, "sheep"], [0, "goat"], [1, "dog"]]
irb(main):137:0> a.sort_by { |s| s[0] }
=> [[0, "cow"], [0, "chicken"], [0, "cat"], [0, "pig"], [0, "sheep"], [0, "goat"], [1, "dog"]]
irb(main):138:0> a.sort_by { |s| s[0] }
=> [[0, "cow"], [0, "chicken"], [0, "cat"], [0, "pig"], [0, "sheep"], [0, "goat"], [1, "dog"]]
irb(main):139:0> a.sort_by { |s| s[0] }
=> [[0, "cow"], [0, "chicken"], [0, "cat"], [0, "pig"], [0, "sheep"], [0, "goat"], [1, "dog"]]
irb(main):140:0> a.sort_by { |s| s[0] }
=> [[0, "cow"], [0, "chicken"], [0, "cat"], [0, "pig"], [0, "sheep"], [0, "goat"], [1, "dog"]]
irb(main):141:0> a.sort_by { |s| s[0] }
=> [[0, "cow"], [0, "chicken"], [0, "cat"], [0, "pig"], [0, "sheep"], [0, "goat"], [1, "dog"]]
irb(main):142:0> a.sort_by! { |s| s[0] }
=> [[0, "cow"], [0, "chicken"], [0, "cat"], [0, "pig"], [0, "sheep"], [0, "goat"], [1, "dog"]]

Upvotes: -1

Related Questions