ランダムソート

誰が「ソートするときに比較関数に『ランダムに1か-1を返す関数』を与えたらシャッフルできる」って言い出したのかしらないけど、真に受ける方も真に受ける方だと思う。

幸い使用したことはないけど、以前なにかの書籍で読んでそのまま鵜呑みにしたことがあるなぁ。。。
どの書籍で読んだのだろうと探してみてまず見つかったのが、『Rubyクックブック』p.53の例

module Enumerable
  def each_randomly
    (sort_by { rand }).each { |e| yield e}
  end
end

ぱっとみて「あ、これだ」と思ったけどsortじゃなくてsort_byなので大きく偏ることはなさそう。ただ厳密な意味でランダムかというと、たまたまrandが同じ数字を返したときとか微妙な気もする。

次に見つけたのが某Ruby書の監注にあった例

sort {.5 <=> rand }

うーん、ダメそう。

irb(main):001:0> result = Hash.new(0)
=> {}
irb(main):002:0> 1.upto(7000) {result[[0,1,2,3,4,5,6].sort{ 0.5 <=> rand}[0]] += 1}
=> 1
irb(main):003:0> Array(result).sort.each {|key, val| puts "%d %d" % [key, val]}
0 1114
1 958
2 1042
3 693
4 1172
5 967
6 1054
=> [[0, 1114], [1, 958], [2, 1042], [3, 693], [4, 1172], [5, 967], [6, 1054]]

先頭に3が全然こないよ。
もともと件の書籍ではランダム化の方法として

class Array
  def randomize!
    result = collect {slice! (rand length)}
    replace result
  end
end

というのが紹介されていて、本文に「もし読者がこれよりうまい方法を見つけたら、ぜひ私たちに教えてください。」とあり、それに対する監注として上の例が挙げられていたので、まんまと釣られてしまったというところなのだろうか。