Sort stability: Difference between revisions

→‎{{header|Ruby}}: Distinguish JRuby from MRI.
(→‎{{header|Ruby}}: Distinguish JRuby from MRI.)
Line 558:
 
=={{header|Ruby}}==
Ruby's built-in sort methods use(Array#sort, Array#sort_by, Enumerable#sort and Enumerable#sort_by) are not stable. [[MRI]] uses [[Sorting algorithms/Quicksort|quicksort]], which is not stable[ [http://groups.google.com/group/comp.lang.ruby/msg/2a6c50d173a902da? (1])]. It seems that stable sorting is not worth the performance trade-off; MRI rejected a proposal to switch to a stable sort [http://redmine.ruby-lang.org/issues/show/1089 (2)].
 
<lang ruby>ary = [["UK", "London"], ["US", "New York"], ["US", "Birmingham"], ["UK", "Birmingham"]]
{{works with|MRI|1.8.7, 1.9.2}}
ary.sort {|a,b| a[1] <=> b[1]}
<lang ruby>ary = [["UK", "London"],
["US", "New York"],
["US", "Birmingham"],
["UK", "Birmingham"]]
p ary.sort {|a,b| a[1] <=> b[1]}
# MRI reverses the Birminghams:
# => [["UK", "Birmingham"], ["US", "Birmingham"], ["UK", "London"], ["US", "New York"]]</lang>
 
Other implementations of Ruby might differ. Old versions of [[JRuby]] used java.util.Arrays.sort, which is a stable sort, but is slower than MRI. To increase performance, JRuby switched to quicksort, which is not stable. [http://jira.codehaus.org/browse/JRUBY-2198 (3)]
There seems to be some discussion debating whether stable sorting is worth the performance trade-off [[http://redmine.ruby-lang.org/issues/show/1089 2]].
 
<!--
To code a stable sort[[http://codesnippets.joyent.com/posts/show/1698 2]]:
Anonymous user