Rosetta Code

Sort stability: Difference between revisions

Page Discussion

Sort stability (view source)

Revision as of 16:50, 17 September 2011

504 bytes added ,  12 years ago
→‎{{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
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/114340"