Java によるソートキラー のページで、 あらゆるソートアルゴリズムが対象のソートキラーの Java による実装を示しました。 ソートキラーとは、与えられた任意のソートアルゴリズムの、 最も苦手とするワーストケースの系列を求めるものです。つまり、 ソートキラーで計算した系列をソートすると、 そのソートアルゴリズムの最悪計算量になるわけです。
しかし、このソートキラーの計算量は \(O(N^3 + f(N))\) と大きく(\(f(N)\) はソートアルゴリズムの計算量)、 例えば、最悪計算量 \(O(N^2)\) に陥ることを回避できるアルゴリズムが、 実際に回避に成功するか確認したいという場合に不便です(\(N\) は要素数)。 100万個の要素で動かしたりすると、うんともすんとも言わなくなります。
で、実際、最悪計算量に陥るかどうか興味があるのは、 たぶんクイックソートくらいですよね普通。 まあ、私はコムソートの最悪計算量とかにも興味がありましたけどね(^^; そこで、クイックソート専用のクイックソートキラーを実装してみました。 \(O(N^2)\) になるのが回避できていれば、すぐにコンソールに帰ってきます。
実行すると、クイックソートのワーストケース系列を Arrays.sort でソートした場合のソート時間と比較回数対 \(N^2\) との比、 クイックソートでソートした場合のソート時間と比較回数対 \(N^2\) との比をそれぞれ表示します(\(N\) は要素数)。
とりあえず、デフォルトの要素数 \(N\) は 10000 にしてありますが、 \(O(N^2)\) を回避できるアルゴリズムの場合は \(N\) = 1000000 とかにして確認します。 ただし、何の工夫もしてないクイックソートの場合、\(N\) = 100000 で実行するには java -Xss256m QuickSortKiller と、 スタックサイズを指定してやる必要があります。さらに \(N\) = 1000000 の場合はもう、どうあがいてもスタックオーバーフローしちゃいます。
以下に、 クイックソートキラーに適用するクイックソートのコードを示します。 これを参考に、 みなさんも自分で試したいクイックソートを書いてみてください。 ちなみに、PQuickSort.java, IntroSort.java はクイックソートキラーに適用しても、 \(O(N^2)\) の計算量に陥らない工夫をこらしたクイックソートです。