トップページ   関連リンク: Java によるクイックソートキラー  

Java によるソートキラー

 こちらのページ で「ソートキラー」という面白い話を見つけました。 与えられた任意のソートアルゴリズムの、 最も苦手とするワーストケースの系列を求めるというものです。つまり、 ソートキラーで計算した系列をソートすると、 そのソートアルゴリズムの最悪計算量になるわけです。

 上記のページからリンクをたどると Ruby による実装が見つかります。 しかし、 Ruby でソートプログラムを書きたいという奇特な人は、 ほとんどいないでしょう。遅すぎて話にならないからです。 そこで、ソートキラーを Java に移植してみました。 以下に Java によるソートキラーの実装を示します。 より高速なクイックソート専用クイックソートキラーに興味のある方は こちらのページ へどうぞ。

SortKiller.java

 ただ、このアルゴリズム、 本当にワーストケースの系列を求めているかと言うと微妙です。一応、 クイックソートや挿入ソートではワーストケースが求まっているようですが、 コムソートでは求まらないみたいです。 コムソートは、最近では平均計算量はほぼ\(O(N\log N)\) 最悪計算量は \(O(N^2)\) と言われているようですが、 ソートキラーにコムソートを適用しても最悪計算量にはなりません (\(N\) は要素数)。

 以下に、ソートキラーに適用するソートアルゴリズムのコードを示します。 これを参考に、 みなさんも自分で試したいソートアルゴリズムを書いてみてください。 ちなみに、PQuickSort.java はソートキラーに適用しても、 \(O(N^2)\) の計算量に陥らない工夫をこらしたクイックソートです。

QuickSort.java

InsertionSort.java

CombSort.java

PQuickSort.java

トップページ   関連リンク: Java によるクイックソートキラー