sort()とsort_by()と安定ソートについて

sort_by.rb

# -*- coding: utf-8 -*-

# sort_byの実装イメージ(公式リファレンスより)
class Array
  def sort_by
    self.map {|i| [yield(i), i] }.
      sort {|a, b| a[0] <=> b[0] }.
      map {|i| i[1]}
  end
end

# ちょっと分かり辛いので、どうなってるのか追っかけてみる。

puts "before"
p hoge = (1..10).map {|n| (rand * 1000).to_i}
#=> [870, 480, 957, 227, 438, 603, 877, 219, 523, 112]

# sort_byのブロックの処理結果(ここでは'i % 2'と既に置き換えてある。)と、元の値の2要素からなる配列をmapする
puts "#map(1st)"
p huga = hoge.map {|i|[i % 2, i]}
#=> [[0, 870], [0, 480], [1, 957], [1, 227], [0, 438], [1, 603], [1, 877], [1, 219], [1, 523], [0, 112]]

# ブロックの処理結果をもとにsort
puts "#sort"
p piyo = huga.sort {|a, b| a[0] <=> b[0] }
#=> [[0, 870], [0, 480], [0, 438], [0, 112], [1, 227], [1, 957], [1, 877], [1, 219], [1, 523], [1, 603]]

# 元の値をmapする
puts "#map(2nd)"
p piyo.map {|i| i[1]}
#=> [870, 480, 438, 112, 227, 957, 877, 219, 523, 603]

# 2で割った余りは0と1の2つの値しか無い。0のグループ・1のグループでの元の順番は保持されていない
# これとは逆に、比較結果が同じ要素は元の順序通りに並ぶソートを 「安定なソート (stable sort)」と言う
puts "after"
p hoge.sort_by {|item| item % 2}
#=> [870, 480, 438, 112, 227, 957, 877, 219, 523, 603] 

# sort()はどうだっけ？
puts "#sort"
p hoge.sort {|a, b| a % 2 <=> b % 2}
#=> [870, 480, 438, 112, 227, 957, 877, 219, 523, 603]
# "ブロック内の処理(ここでは'%()')が要素数以上に呼び出される事になる。これが重たい処理だったりすると結構影響するらしい"

# 安定ソートを実装するには？
puts "stable sort"
i = 0
p hoge.sort_by {|v| [v % 2, i += 1] }
#=> [870, 480, 438, 112, 957, 227, 603, 877, 219, 523]
# たしかに、0のグループと1のグループの登場順を守ってソートされている。
# sort_byの実装イメージを思い出すと分かりやすい。内部的にインデックスを利用する、という事なんだね。