Ответ 1

И сортировка МРТ и sort_by нестабильны. Некоторое время назад была просьба сделать их стабильными, но она была отвергнута. Причина: Ruby использует алгоритм быстрой сортировки на месте, который работает лучше, если стабильность не требуется. Обратите внимание, что вы все равно можете использовать стабильные методы из нестабильных:

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

Ответ 2

Нет, встроенный сорт ruby ​​нестабилен.

Если вы хотите стабильную сортировку, это должно сработать. Вероятно, вы захотите создать для него метод, если вы собираетесь использовать его часто.

a.each_with_index.sort_by {|h, idx| [h[:int], idx] }.map(&:first)

В основном он отслеживает исходный индекс массива каждого элемента и использует его как тай-брейк, когда h[:int] - то же самое.

Дополнительная информация для любопытных:

Насколько я знаю, использование исходного индекса массива в качестве тай-брейкера - единственный способ гарантировать стабильность при использовании нестабильной сортировки. Фактические атрибуты (или другие данные) предметов не сообщают вам их первоначальный порядок.

Ваш пример несколько надуман, потому что клавиши :id сортируются по возрастанию в исходном массиве. Предположим, что исходный массив отсортирован по убыванию :id; вы хотите, чтобы :id в результате спускался при разрыве соединения, например:

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

Использование исходного индекса также будет обрабатывать это.

Update:

Мать собственное предложение (см. эта страница) аналогична и может быть немного более эффективной, чем указано выше:

n = 0
ary.sort_by {|x| n+= 1; [x, n]}

Ответ 3

Для некоторых реализаций Ruby сортировка стабильна, но вы не должны зависеть от нее. Стабильность сортировки Ruby определяется реализацией.

Что говорится в документации

В документации говорится, что вы не должны зависеть от того, насколько сортировка стабильна:

Результат не гарантируется. Когда сравнение двух элементов возвращает 0, порядок элементов непредсказуем.

Обратите внимание, что это не говорит о том, стабилен ли тип. Он просто говорит, что не гарантируется стабильность. Любая реализация Ruby может иметь стабильный вид и по-прежнему соответствовать документации. Он также может иметь нестабильный вид или изменить, является ли сортировка стабильной в любое время.

Что Ruby действительно делает

Этот тестовый код печатает true, если сортировка Ruby стабильна или false, если это не так:

Foo = Struct.new(:value, :original_order) do
  def <=>(foo)
    value <=> foo.value
  end
end

size = 1000
unsorted = size.times.map do |original_order|
  value = rand(size / 10)
  Foo.new(value, original_order)
end
sorted = unsorted.sort
stably_sorted = unsorted.sort_by do |foo|
  [foo.value, foo.original_order]
end
p [RUBY_PLATFORM, RUBY_VERSION, RUBY_PATCHLEVEL, sorted == stably_sorted]

Вот результаты для всех Rubies, которые я установил в своем Linux-боксе:

["java", "1.8.7", 357, false]
["java", "1.9.3", 551, false]
["x86_64-linux", "1.8.7", 374, false]
["x86_64-linux", "1.8.7", 374, false]
["x86_64-linux", "1.8.7", 376, false]
["x86_64-linux", "1.9.3", 392, false]
["x86_64-linux", "1.9.3", 484, false]
["x86_64-linux", "1.9.3", 551, false]
["x86_64-linux", "2.0.0", 643, false]
["x86_64-linux", "2.0.0", 648, false]
["x86_64-linux", "2.1.0", 0, false]
["x86_64-linux", "2.1.10", 492, false]
["x86_64-linux", "2.1.1", 76, false]
["x86_64-linux", "2.1.2", 95, false]
["x86_64-linux", "2.1.3", 242, false]
["x86_64-linux", "2.1.4", 265, false]
["x86_64-linux", "2.1.5", 273, false]
["x86_64-linux", "2.1.6", 336, false]
["x86_64-linux", "2.1.7", 400, false]
["x86_64-linux", "2.1.8", 440, false]
["x86_64-linux", "2.1.9", 490, false]
["x86_64-linux", "2.2.0", 0, true]
["x86_64-linux", "2.2.1", 85, true]
["x86_64-linux", "2.2.2", 95, true]
["x86_64-linux", "2.2.3", 173, true]
["x86_64-linux", "2.2.4", 230, true]
["x86_64-linux", "2.2.5", 319, true]
["x86_64-linux", "2.2.6", 396, true]
["x86_64-linux", "2.3.0", 0, true]
["x86_64-linux", "2.3.1", 112, true]
["x86_64-linux", "2.3.2", 217, true]
["x86_64-linux", "2.3.3", 222, true]
["x86_64-linux", "2.4.0", 0, true]
["x86_64-linux", "2.4.0", -1, true]
["x86_64-linux", "2.4.0", -1, true]
["x86_64-linux", "2.4.0", -1, true]
["x86_64-linux", "2.4.0", -1, true]
["x86_64-linux", "2.4.1", 111, true]

Мы видим, что JRuby нестабилен, а MRI до 2.2, в Linux, нестабилен. MRI >= 2.2.0 является стабильным (опять же, в Linux).

Однако платформа имеет значение. Хотя приведенный выше результат показывает, что сортировка стабильна в MRI 2.4.1 в Linux, такая же версия нестабильна в Windows:

["x64-mingw32", "2.4.1", 111, false]

Почему сортировка МРТ стабильна в Linux, но не в Windows?

Даже в пределах одной версии Ruby-реализации алгоритм сортировки может измениться. МРТ может использовать как минимум три разных типа. Процедура сортировки выбирается во время компиляции, используя серию #ifdefs в util.c. Похоже, что МРТ имеет возможность использовать сортировки по меньшей мере из двух разных библиотек. Он также имеет свою собственную реализацию.

Что вам следует делать?

Так как сортировка может быть стабильной, но не может быть гарантирована стабильностью, не записывайте код, который зависит от того, какой тип Ruby является стабильным. Этот код может сломаться при использовании в другой версии, реализации или платформе.

Ответ 4

лично я не стал бы рассчитывать на это. Как сделать что-то подобное:

a.sort {|a, b| s1 = a[:int] <=> b[:int]; s1 != 0 ? s1 : a[:id] <=> b[:id] }