sortとsort_by - rochefort's blog

安定ソート

と、その前にこれが理解できてないのでこっちを整理。

Enumerable#sort は安定ではありません (unstable sort)。
Enumerable#sort_by は安定ではありません (unstable sort)。
註：比較結果が同じ要素は元の順序通りに並ぶソートを「安定なソート (stable sort)」と言います。

リファレンス読んでも、パッと理解できなかったので
安定ソート - Wikipediaを見て納得。

安定ソート（あんていソート、stable sort）とは、ソート（並び替え）のアルゴリズムのうち、
同等なデータのソート前の順序が、ソート後も保存されるものをいう。
つまり、ソート途中の各状態において、常に順位の位置関係を保っていることをいう。
たとえば、学生番号順に整列済みの学生データを、テストの点数順で安定ソートを用いて並べ替えたとき、
ソート後のデータにおいて、同じ点数の学生は学生番号順で並ぶようになっている。

2次元配列を使って確認。

（要素1には乱数、要素2にはindexを入れた配列を20個用意して、要素1でソート）

irb(main):001:0> ary = []
=> []
irb(main):002:0> 1.upto(20) {|v| ary << [rand(v), v] }
=> 1
irb(main):003:0> p ary
[[0, 1], [0, 2], [2, 3], [1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [3, 9], [3, 10], [4, 11], [11, 12], [12, 13], [11, 14], [6, 15], [4, 16], [2, 17], [11, 18], [16, 19], [2, 20]]
=> nil
irb(main):004:0> ary.sort {|x,y| x[0] <=> y[0]}
=> [[0, 1], [0, 2], [0, 6], [1, 4], [2, 17], [2, 3], [2, 20], [3, 8], [3, 9], [3, 5], [3, 10], [4, 16], [4, 11], [5, 7], [6, 15], [11, 12], [11, 18], [11, 14], [12, 13], [16, 19]]
irb(main):005:0> ary.sort_by{|x| x[0]}
=> [[0, 1], [0, 2], [0, 6], [1, 4], [2, 17], [2, 3], [2, 20], [3, 8], [3, 9], [3, 5], [3, 10], [4, 16], [4, 11], [5, 7], [6, 15], [11, 12], [11, 18], [11, 14], [12, 13], [16, 19]]

要素1（乱数）でソートされているものの、要素2（index）ではソートされていない。
なるほどこういうことなんですね。

実は安定ソートが書ける

リファレンスに記載されてる通りなんだけど

irb(main):010:0 i = 0
=> 0
irb(main):011:0> ary.sort_by {|v| [v[0], i += 1] }
=> [[0, 1], [0, 2], [0, 6], [1, 4], [2, 3], [2, 17], [2, 20], [3, 5], [3, 8], [3, 9], [3, 10], [4, 11], [4, 16], [5, 7], [6, 15], [11, 12], [11, 14], [11, 18], [12, 13], [16, 19]]

おお、できた。

ちなみに、sortをブロック無しで使うと

irb(main):012:0> ary.sort
=> [[0, 1], [0, 2], [0, 6], [1, 4], [2, 3], [2, 17], [2, 20], [3, 5], [3, 8], [3, 9], [3, 10], [4, 11], [4, 16], [5, 7], [6, 15], [11, 12], [11, 14], [11, 18], [12, 13], [16, 19]]

安定してるように見えるけど、実際には小さい配列の2つの要素を比較してるからなんでしょう。

sortとsort_byの違い

さぁ、ここでようやく本題。
リファレンスのようにdowncaseを呼び出す例を考えると

sortは比較の度に呼び出してしまうため
呼び出すメソッドや要素数によってはボトルネックになってしまう。

一方sort_byでは、要素1にブロック(downcase)の値、
要素2に元(downcase前)の値を持つ2次元配列を生成し、
要素1でソートをしておいて要素2の値を返す。

sort_byとほぼ同じソース。

class Array
  def sort_by
    self.collect {|i| [yield(i), i] }.
       sort {|a,b| a[0] <=> b[0] }.
       collect! {|i| i[1]}
  end
end

なのでdowncaseの評価回数は要素数と同じになる。
ということらしい。
なるほど。

実行例

irb(main):001:0> class Integer
irb(main):002:1>   def count
irb(main):003:2>     $n += 1
irb(main):004:2>     self
irb(main):005:2>   end
irb(main):006:1> end

irb(main):007:0> 1.upto(20) {|v| ary << [rand(v), v] }
=> 1

irb(main):010:0> $n = 0
ary.sort {|x,y| x[0].count <=> y[0].count}
irb(main):012:0> p $n
114
irb(main):017:0> ary.sort_by{|x| x[0].count}
irb(main):018:0> p $n
20

See Also

安定ソート

2次元配列を使って確認。

実は安定ソートが書ける

sortとsort_byの違い

実行例