Anonymous user
Sort stability: Difference between revisions
→{{header|Ruby}}: documenting difficulties
m (d'oh!) |
(→{{header|Ruby}}: documenting difficulties) |
||
Line 29:
=={{header|Ruby}}==
Ruby's built-in sort methods use quicksort which is not stable[[http://groups.google.com/group/comp.lang.ruby/msg/2a6c50d173a902da? 1]].
<lang ruby>ary = [["UK", "London"], ["US", "New York"], ["US", "Birmingham"], ["UK", "Birmingham"]]
ary.sort {|a,b| a[1] <=> b[1]}
# => [["UK", "Birmingham"], ["US", "Birmingham"], ["UK", "London"], ["US", "New York"]]</lang>
To code a stable sort[[http://codesnippets.joyent.com/posts/show/1698 2]]:
<lang ruby>class Array
def stable_sort
Line 43 ⟶ 48:
end
end</lang>
However, even that is insufficiently general. Consider:
<lang ruby>ary.stable_sort {|a,b| a[1] <=> b[1]}
# => [["UK", "London"], ["US", "New York"], ["US", "Birmingham"], ["UK", "Birmingham"]]</lang>
Above, we end up sorting by the generated index number because the temporary array has nested the original array elements "x" into subarrays "[x, n]". We are required to know the structure of the temporary array:
<lang ruby>ary.stable_sort {|a,b| (a[0][1] <=> b[0][1]).nonzero? or a[1]<=>b[1]}
# => [["US", "Birmingham"], ["UK", "Birmingham"], ["UK", "London"], ["US", "New York"]]</lang>
So, if we want to use Ruby's <code>sort</code> ''and'' we want stability, we might be better off using a custom Schwartzian transform:
<lang ruby>
ary.each_index \
.map {|i| ary[i] + [i]} \
.sort {|a,b| (a[1] <=> b[1]).nonzero? or a[-1] <=> b[-1]} \
.map {|x| x.pop; x}
# => [["US", "Birmingham"], ["UK", "Birmingham"], ["UK", "London"], ["US", "New York"]]</lang>
=={{header|Tcl}}==
| |||