しまった、同じ書き出しだったけど昨日このネタ書いてたので削除した。疲れてるっぽい(笑)。とほほ。
まぁそれはさておき、話のつづき。あの後、クイックソートでリスト長が5にしてみたところ、けっこう直感に反する結果になって楽しんだりした。なぜかというと入れ替えのパターンが相当数に上るため。全パターンを列挙して確率計算するのはけっこう面倒だ(昨晩、頭の中で考えて破綻した)。
それから、「sort{rand-0.5}でも一様に分布するシャッフル」というのをちょっと考えて、マージソートはどうか、と考えて実際に試してみた。で、やってから気付いたのだが、長さが2のべき乗の配列の場合、マージソートでは sort{rand-0.5} でも一様に分布する。しかし、2のべき乗でないなら偏りが生じる。
他のソート法はどうかというと、いちおう単純選択ソートで試してみてしまってから気付いたけど、まぁ無理でしょうな。単純選択ソートや挿入ソートの場合は、最後の要素が最初に来やすくなる。コームソートやシェルソートはどうだろう？ あんま変わらない気もするけれど。
まぁ偏り方はそれぞれだろうけど。