【Ruby】2次元配列におけるsortとsort_byの安定性
記事の概要
この記事の結論
- rubyの
sortメソッドとsort_byメソッドは基本的にstableではないので、2次元以上の配列の並び替えではsort_byメソッドを使用し、書き方に注意する。
実行環境
- ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) [x86_64-linux]
対象読者
- ruby初学者、実務未経験
今回考える問題では、入力の各要素の2番目要素で降順に並び替え、その後1番目要素で降順に並び替えます。
# 入力
input = [[2,3],[0,4],[5,0],[3,3]]
# 期待する出力
output = [[0,4],[3,3],[2,3],[5,0]]
この並び替えは次の式で実現できます。
array.sort_by!{ |a| [-a[1], -a[0]] }
-a[i]で、i番目の要素で降順ソートをします。
sortメソッドでの実装検討
※結局sortメソッドを使用した解法はわからなかったので、間違い等あればコメントいただけると幸いです。
問題に取り掛かったとき、最初は以下のようにsortメソッドでの解法を考えていました。
array.sort!{[a,b] b[1] <=> a[1] || b[0] <=> a[0]}
比較演算子<=>は、順序が合っていれば１，逆なら-1、同じ数字なら0を返します。
つまりb[1] <=> a[1]が1なら順序はそのまま、-1を返したら順序を逆にし、0なら次のb[0] <=> a[0]を評価します。
（b[i] <=> a[i]は降順、a[i] <=> b[i]は昇順にソートされます。）
ただ、出力は以下のようになっていました。
0 4
2 3 # #の2行が逆
3 3 #
5 0
これは「ソートの安定性」によるものだそうです。
ソートの安定性とは
以下の記事が参考になりました。
どうやらrubyのsortアルゴリズムはQuickSortというものになっているようで、QuickSortは値が等しい時に順番が崩れてしまうとのことです。
この影響で期待する出力を得られていないようでした。
（安定性のことをstableと言うようです。）
リファレンスを見ると、sortメソッドもsort_byメソッドもstableではないようです。
sort_byメソッドで以下のような書き方をするとstableになります。
ブロックの中の[]の書き方が重要そうです。
i = 0
ary.sort_by {|v| [v, i += 1] }
おまけ sortとsort_byの実行速度の違い
リファレンスにもありますが、sortにブロックを渡したとき、比較演算子<=>の両辺にメソッドを使うと膨大な計算量になります。
sort_byの方が早いみたいです。
詳細はリファレンスをご確認ください。
Railsでアプリを作るときにも気にしておきたいです。
以上です。ありがとうございました。
Discussion
これ、sortでうまくいっていないのはsortの安定性とは関係なく(厳密には最後に関係するのですが)、Rubyの数値型の真偽性によるものです。
Rubyで偽と扱われるのはfalseとnilのみであるため、0はfalseではなくtrueと扱われます。
このため、前段の
b[1] <=> a[1]が常に真と判断され、後段のb[0] <=> a[0]はb[1] == a[1]の場合も実行されない、というのが真相です。結果として、sortが安定であることから、元の順序性が維持されることにより、記事にあるような結果が得られるのです。
とはいえ、これでは使いづらい場合がありますので、Numeric#nonzero? というメソッドが用意されています。ゼロの場合nil(偽)を、そうでない場合self(元の値)を返すという、UFO演算子のチェインに使うために用意されたような便利メソッドです。
sortを使う場合、これを用いて以下のようにすればうまくいくはずです。
ご参考まで。