【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