Sort stability: Difference between revisions
Content added Content deleted
(→{{header|Ruby}}: Distinguish JRuby from MRI.) |
|||
Line 558: | Line 558: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
Ruby's built-in sort methods |
Ruby's built-in sort methods (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}} |
|||
⚫ | |||
<lang ruby>ary = [["UK", "London"], |
|||
["US", "New York"], |
|||
["US", "Birmingham"], |
|||
["UK", "Birmingham"]] |
|||
⚫ | |||
# MRI reverses the Birminghams: |
|||
# => [["UK", "Birmingham"], ["US", "Birmingham"], ["UK", "London"], ["US", "New York"]]</lang> |
# => [["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]]: |
To code a stable sort[[http://codesnippets.joyent.com/posts/show/1698 2]]: |