Sia l’ ordinamento e l’ ordinamento della MRI sono instabili . Qualche tempo fa c’era una richiesta di renderli stabili, ma è stata respinta. Il motivo: Ruby utilizza un algoritmo di quicksort sul posto , che offre prestazioni migliori se non è richiesta la stabilità. Nota che puoi ancora implementare metodi stabili da quelli instabili:

 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 

No, l’ordinamento predefinito di ruby ​​non è stabile.

Se vuoi un ordinamento stabile, questo dovrebbe funzionare. Probabilmente vorresti creare un metodo per questo se lo userai spesso.

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

Fondamentalmente tiene traccia dell’indice di array originale di ogni elemento e lo usa come tie-breaker quando h[:int] è lo stesso.

Maggiori informazioni, per i curiosi:

Per quanto ne so, l’uso dell’indice di array originale come tie-breaker è l’unico modo per garantire la stabilità quando si utilizza un ordinamento instabile. Gli attributi attuali (o altri dati) degli articoli non ti diranno il loro ordine originale.

Il tuo esempio è un po ‘forzato perché le chiavi :id sono ordinate in ordine crescente nell’array originale. Supponiamo che l’array originale sia stato ordinato decrescente per :id ; vorresti che :id nel risultato sia decrescente quando tie-break, in questo modo:

 [ {: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} ] 

Usare l’indice originale gestirà anche questo.

Aggiornare:

Il suggerimento di Matz (vedi questa pagina ) è simile e potrebbe essere leggermente più efficiente di quanto sopra:

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

Per alcune implementazioni di Ruby, sort è stabile, ma non devi dipendere da esso. La stabilità di Ruby è definita dall’implementazione.

Cosa dice la documentazione

La documentazione dice che non dovresti dipendere dal fatto che l’ordinamento sia stabile:

Il risultato non è garantito per essere stabile. Quando il confronto di due elementi restituisce 0, l’ordine degli elementi è imprevedibile.

Nota che questo non dice se l’ordinamento è stabile o meno. Dice solo che non è garantito che sia stabile. Qualsiasi implementazione data di Ruby potrebbe avere un ordinamento stabile e comunque essere coerente con la documentazione. Potrebbe anche avere un ordinamento instabile o cambiare se l’ordinamento è stabile in qualsiasi momento.

Cosa fa in realtà Ruby

Questo codice di test viene stampato true se l’ordinamento di Ruby è stabile o false se non lo è:

 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] 

Ecco i risultati di tutti i Ruby che ho installato sulla mia macchina 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] 

Possiamo vedere che JRuby è instabile, e la risonanza magnetica prima della 2.2, su Linux, è instabile. MRI> = 2.2.0 è stabile (di nuovo, su Linux).

La piattaforma conta, però. Anche se il risultato sopra mostra che sort è stabile in MRI 2.4.1 su Linux, la stessa versione è instabile su Windows:

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

Perché la risonanza magnetica è stabile su Linux, ma non su Windows?

Anche all’interno di una singola versione di un’implementazione di Ruby, l’algoritmo di ordinamento può cambiare. La risonanza magnetica può utilizzare almeno tre diversi tipi. La routine di ordinamento viene selezionata al momento della compilazione utilizzando una serie di #ifdefs in util.c. Sembra che la risonanza magnetica abbia la possibilità di utilizzare i tipi da almeno due diverse librerie. Ha anche una sua implementazione.

Cosa dovresti fare al riguardo?

Dato che l’ordinamento può essere stabile ma non può essere garantito che sia stabile, non scrivere codice che dipenda dal fatto che il tipo di Ruby sia stabile. Tale codice potrebbe interrompersi se utilizzato su una versione, un’implementazione o una piattaforma diversa.

personalmente non ci conterei. Come fare una cosa del genere:

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