Quicksort の攻撃方法
以前 Quicksort の計算量について話したので、ブログにも書いておきます。
参考にしたのは、 M. D. MCILROY の A Killer Adversary for Quicksort です。
Quicksort は、 pivot の選択方法がまずいとオーダが になってしまうという弱点があります。
まずい選択というのは、分割対象の数列の最小（最大）の要素をpivotにしてしまうときで、そのような場合は、最小（最大）の値を含むものと、それ以外の集合に分割されてしまい、結局選択ソートと似たような挙動になってしまいます。
そこで、通常は各区間の「左端」・「中央」・「右端」の3つの値をとってきて*1、その中央値をpivotとするといった実装がよく見られます。
ところが、この手法にも問題があり、工夫されたデータ列に対してはやはり になってしまいます。詳細についてはスライドを参照していただきたいのですが、一部の実装ではまさにこの方法でpivotの選択が行われており、攻撃データを入力すると処理が終わらなくなってしまいます（PHPの場合はタイムアウトする）。
これらを完全に避けるためには、 Introsort のようなクイックソートを改良したものを使ったり、 Timsort のようなクイックソート以外のアルゴリズムをベースにしたものを使う必要があります。
また、 Quicksort でもpivotの選択方法を乱択にすることでこれらの問題を回避することができます。単純な実装としては、ランダムな位置から3つの要素を取ってきて、その中央値をとるなどの方法が考えられます。
*1:メモリ上のデータに右や左はありませんが…
