Ruby 中的排序是否稳定? [英] Is sort in Ruby stable?

问题描述

sort 在 Ruby 中稳定吗?也就是说，对于 sort 并列的元素，它们之间的相对顺序是否保留了原始顺序?例如，给定:

a = [{id: :a, int: 3},{id: :b, 整数: 1},{id: :c, int: 2},{id: :d, int: 0},{id: :e, 整数: 1},{id: :f, int: 0},{id::g, int: 1},{id: :h, int: 2},]

是否保证我们总是得到

a.sort_by{|h|暗示]}

以下

<预><代码>[{id: :d, int: 0},{id: :f, int: 0},{id: :b, 整数: 1},{id: :e, 整数: 1},{id::g, int: 1},{id: :c, int: 2},{id: :h, int: 2},{id: :a, int: 3},]

:id 值为 :d、:f 和 的元素之间的相对顺序没有任何变化:b、:e、:g，还有:c、:h?如果是这种情况，在文档中的哪个位置对其进行了描述?

这个问题可能与这个问题有关，也可能没有.

解决方案

Both MRIsort 和 sort_by 是 不稳定.前段时间有一个请求让它们稳定，但被拒绝了.原因:Ruby 使用就地快速排序算法，如果不需要稳定性，它的性能会更好.请注意，您仍然可以从不稳定的方法中实现稳定的方法:

module 可枚举def stable_sortsort_by.with_index { |x, idx|[x, idx] }结尾def stable_sort_bysort_by.with_index { |x, idx|[产量(x), idx] }结尾结尾

Is sort in Ruby stable? That is, for elements that are in a tie for sort, is the relative order among them preserved from the original order? For example, given:

a = [
  {id: :a, int: 3},
  {id: :b, int: 1},
  {id: :c, int: 2},
  {id: :d, int: 0},
  {id: :e, int: 1},
  {id: :f, int: 0},
  {id: :g, int: 1},
  {id: :h, int: 2},
]

is it guaranteed that we always get for

a.sort_by{|h| h[:int]}

the following

[
  {id: :d, int: 0},
  {id: :f, int: 0},
  {id: :b, int: 1},
  {id: :e, int: 1},
  {id: :g, int: 1},
  {id: :c, int: 2},
  {id: :h, int: 2},
  {id: :a, int: 3},
]

without any variation for the relative order among the elements with the :id value :d, :f, and among :b, :e, :g, and among :c, :h? If that is the case, where in the documentation is it described?

This question may or may not have connection with this question.

解决方案

Both MRI's sort and sort_by are unstable. Some time ago there was a request to make them stable, but it was rejected. The reason: Ruby uses an in-place quicksort algorithm, which performs better if stability is not required. Note that you can still implement stable methods from unstable ones:

module Enumerable
  def stable_sort
    sort_by.with_index { |x, idx| [x, idx] }
  end

  def stable_sort_by
    sort_by.with_index { |x, idx| [yield(x), idx] }
  end
end

这篇关于Ruby 中的排序是否稳定?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！