一番下に追記あります。
最遅ソートアルゴリズム研究会 (beyond the bogosort)
http://twitter.com/#!/y_benjo/status/112915204546887680
というつぶやきを見て、最も遅いソートアルゴリズムは何だろう、ということが気になりはじめました。
もちろん Bogosort や Stooge sort や Permutation sort は遅いです。遅いんですが、これらのソートアルゴリズムは、 明らかに完全に無駄な操作を繰り返すことで時間を稼いでいる面があります。これはズルい。チートです。 ズルくなくて、しかも遅いアルゴリズムは何でしょうか。
自分の疑問をきちんと定義します。 wikipedia:比較ソートの理論限界 にあるように、「比較演算の回数」に着目することで、最速のソートアルゴリズムであっても、 ケースによっては Ω(N log N) 回の比較が必要だ、という議論ができます。 今回はこれに倣って、「比較演算の回数」を「遅さ」の指標ということにしましょう。 「全く情報量のない比較（＝それまでにした比較の結果から考えれば、 やる前から答えが既に確定している比較）を除いた比較演算の回数」 が一番多くなる最遅ソートアルゴリズムは、なんでしょう。
ふつう計算量について考えるときは、最悪計算量と平均計算量とを考えると思いますが、今回もそれに倣います。 ただし、ここでいう最悪とは、当然、「もっとも速く比較が終わってしまうケース」を指します。
まず、N要素のリストなら、全要素どうしの比較をすれば後はそれ以上情報が増えなくなるので、 最多でも N(N-1)/2 回しか比較はできません。つまり、最遅ソートでも比較回数はせいぜい N2 オーダ。 それよりも遅くなることはできません。
バブルソート は、元々の入力がソート済みだった場合、最初の一周で全要素の順番がわかる比較をしてしまいます。 最悪ケースで O(N)。これは速すぎる。 選択ソート は逆順ソートされていた場合が最悪ケースで、やはり最初の一周で情報が完璧に得られてしまいます。 この最悪ケースでは、それ以降は全て無駄な比較をして時間を稼いでいるだけです。
クイックソート は無駄な比較は一切しませんし、ご存じの通り最も比較演算の回数が多くなるケースでのオーダは Θ(N2) なので、場合によっては確かに遅くなります。が、これは最善ケースを考えているだけなので、 大した意味はありません。 重要なのは、クイックソートはどんな入力に対しても常に Ω(N log N) 回の比較をするところです。 バブルソートや選択ソートと比較して、安定して遅い。素晴らしいですね。 クイックソートは平均でも Θ(N log N) の比較回数です。
…という辺りまで考えました。 最速ソートが Ω(N log N) 回の比較を必要とするのと概ね同じ議論で、 最遅ソートでも O(N log N) 回で必ず比較が完了してしまうケースが存在すると思うので、 最悪計算量は、クイックソートが最善を達成しています。 平均はどうでしょう。 平均で Ω(N2) 回の比較をしてしまうソートアルゴリズムは果たしてあるのでしょうか。 バブルソートや選択ソートは、情報量ゼロの比較を何度も繰り返していますが、それらを除いても、 Ω(N2) 回の比較をすることができているのでしょうか。さてさて。
@kinaba N 個のものをソートしてから、N+1 番目のものを N 個のうち小さいほうから順に比較していくと場所を決定するのに平均 N/2 回くらいかかる気がします
http://twitter.com/#!/rng_58/status/113252221449281536
その通りでした！挿入ソートさんが平均で最遅を達成。 これは"最悪"が線形時間ですが、平均が遅いだけでなく、 さらに最悪をN log Nに押さえることができるか等が興味深いところとなってきました。
oxy さんにより、平均 Ω(N2)、最悪でも Ω(N log N) の最遅ソートアルゴリズムが提案されました。 クイックソートと、マージソートの「マージの仕方を間違える」という技の組み合わせ。なるほど！
// http://twitter.com/#!/oxy/status/113260781180686336
// http://twitter.com/#!/oxy/status/113275511156916224
T[] slow_sort( T[] a )
{
T[] b = quick_sort( a[0 ～ a.length/2] ); // 半分に分けて
T[] c = quick_sort( a[a.length/2 ～ $] ); // 両方クイックソート
for(int i=b.length-1; i>=0; --i)
c = insert(c, b[i]); // bの値を"大きい順に"cにマージ
return c;
}
T[] insert( T[] a, T v )
{
for(int i=0; i<a.length; ++i) // 入れる場所は"小さい順に"調べる
if( v < a[i] )
return a[0 ～ i] + [v] + a[i ～ $];
return a + [v];
}
長さ半分の配列をクイックソートする分の比較回数は確実に使うので、その分で、最悪 Ω(N log N) は保証。 最後のお馬鹿マージステップが、最悪の場合、b の末尾より c の先頭の方が大きかった場合は、 最初の１回目の比較で全ての順位が決まってしまいますが、平均的には、 b と c はだいたい似たような大きさにばらけるはずで、マージの際に c の中に b の要素が均等に散らばる感じになると思うので、結果、有意味な比較を N/2 + N/2-1 + ... + 1 回に近い回数行う、 はず。厳密な議論は自分はまだちょっとできてないですが、直感的に確かに行けそうです。