こういう系統の話。
ただのクイックソートは要素数 N の配列をソートするのに最悪 N2 オーダの時間がかかってしまう、 そしてそれは pivot を偏って選びまくってしまった時に発生する、というのはよく知られた話だと思います。 といっても、広く使われている言語／ライブラリのソート関数はその辺り気をつけられていて、最悪時も O(N log N) になるアルゴリズムで実装されている…と思い込んでいたのですが（例えば C++ の std::sort は O(N log N) でなければ言語仕様違反）、そうでもないんですね、と最近知って面白かった。これ：
Java 6 や 7 の java.util.Arrays.sort のいじめ方。プログラミングコンテスト界隈で最近流行しているらしく、 入力された10万個の int 配列をソートする、というコードをそのまま Arrays.sort で実装すると攻撃者に狙われる事案が相次いでいるとか。
Java のソートというと、
TimSort (田中さんの解説)
のようなマージソート系で実装されているとばかり思っていたのですが、
TimSort が使われているのは Object[] のソートと Collections.sort による List<T>
の場合で、プリミティブ型の配列のソートは DualPivotQuicksort というクラスで
// OpenJDK のソースから引用
public class Arrays {
public static void sort(int[] a) {
DualPivotQuicksort.sort(a);
}
public static <T> void sort(T[] a, Comparator<? super T> c) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, c);
else
TimSort.sort(a, c);
}
}
そこでは名前の通りクイックソートを
final class DualPivotQuicksort {
private static final int MAX_RUN_COUNT = 67;
public static void sort(int[] a, int left, int right) {
...
// Check if the array is nearly sorted
for (int k = left; k < right; run[count] = k) {
if (a[k] < a[k + 1]) {
while (++k <= right && a[k - 1] <= a[k]);
} else ...
/*
* The array is not highly structured,
* use Quicksort instead of merge sort.
*/
if (++count == MAX_RUN_COUNT) {
sort(a, left, right, true); // quicksort
return;
}
}
...
}
}
配列が元々ほぼソート済みでなければ （← 67回以上値のアップダウンが切り替わったら） という条件で実行していました。 逆に言うと、DualPivotという工夫はあれども、 この関門をくぐり抜けたら最悪ケースへの防壁がないので狙える、と。 確かに API Reference にも全てのデータに対してO(N log N)とはどこにも書いてない。なるほど。
現状でユーザとして対策するとすれば、Integer[] か ArrayList<Integer>
を常に使う、ということになるのかな。しかし、これが問題になるようなサイズだと Boxing
のオーバーヘッドも避けたくて生配列使ってたりするという面もある気がするので、sort
の前に適当にランダムシャッフルを入れる、くらいなのでしょうか。はてさて。