こちらのページ で「ソートキラー」という面白い話を見つけました。 与えられた任意のソートアルゴリズムの、 最も苦手とするワーストケースの系列を求めるというものです。つまり、 ソートキラーで計算した系列をソートすると、 そのソートアルゴリズムの最悪計算量になるわけです。
上記のページからリンクをたどると Ruby による実装が見つかります。 しかし、 Ruby でソートプログラムを書きたいという奇特な人は、 ほとんどいないでしょう。遅すぎて話にならないからです。 そこで、ソートキラーを Java に移植してみました。 以下に Java によるソートキラーの実装を示します。 より高速なクイックソート専用クイックソートキラーに興味のある方は こちらのページ へどうぞ。
ただ、このアルゴリズム、 本当にワーストケースの系列を求めているかと言うと微妙です。一応、 クイックソートや挿入ソートではワーストケースが求まっているようですが、 コムソートでは求まらないみたいです。 コムソートは、最近では平均計算量はほぼ\(O(N\log N)\) 最悪計算量は \(O(N^2)\) と言われているようですが、 ソートキラーにコムソートを適用しても最悪計算量にはなりません (\(N\) は要素数)。
以下に、ソートキラーに適用するソートアルゴリズムのコードを示します。 これを参考に、 みなさんも自分で試したいソートアルゴリズムを書いてみてください。 ちなみに、PQuickSort.java はソートキラーに適用しても、 \(O(N^2)\) の計算量に陥らない工夫をこらしたクイックソートです。