クイックソートとマージソート

クイックソートはどこで遅くなるのか

クイックソートは、基準がいつも山の一番端の値になると、1 回分けても 1 個しか減らず、遅いソートと同じ n(n − 1) / 2 回まで落ちます。

並んだデータを渡すと最悪になる

先頭を基準にするクイックソートに、もともと小さい順に並んだデータを渡します。先頭はいつも山の中で一番小さい値なので、左の山はいつも空です。

次のコードは、同じ件数で、混ぜたデータ (i × 37 を件数で割った余りで並べ替えた数) と、並んだデータを比べます。出力は、件数、データの種類、基準と比べた回数、分ける段の深さです。

件数 比べた回数 深さ
100 混ぜた 616 11
100 並んだ 4950 100
200 混ぜた 1708 16
200 並んだ 19900 200
400 混ぜた 4320 20
400 並んだ 79800 400

400 件で、混ぜたデータは 4320 回、深さ 20 段で済みました。並んだデータは 79800 回で、これは 400 × 399 / 2 そのものです。深さも 400 段で、1 段に 1 個ずつしか減っていません。件数が 2 倍になるたびに、並んだデータの回数は 4950、19900、79800 と約 4 倍ずつ増え、遅いソートと同じ形です。

深さが件数と同じになるのも危険です。分ける処理を関数の呼び出しで書いていると、呼び出しが件数の分だけ積み重なります。Python では、呼び出しが深くなりすぎると RecursionError で止まります。基準の選び方を変えるか、分けたあと小さい方の山だけを呼び出しで片付け、大きい方の山はループで続ける書き方にすると、深さを抑えられます。

基準の選び方と、分け方で直す

基準の選び方を変えると、並んだデータでも速くなります。ただし、全部が同じ値のデータでは、選び方だけでは直りません。

次のコードは 400 件で、基準を先頭 (first)、真ん中の位置 (middle)、先頭と真ん中と末尾の 3 つの中央値 (med3) にした場合を比べます。最後の 3分割 は、基準と同じ値を別の山に集め、小さい、同じ、大きいの 3 つに分ける書き方です。出力は、基準と比べた回数と深さです。

並んだ
  first 79800 400
  middle 2698 9
  med3 2698 9
  3分割 2698 9
逆順
  first 79800 400
  middle 2698 9
  med3 2698 9
  3分割 2698 9
全部同じ
  first 79800 400
  middle 79800 400
  med3 79800 400
  3分割 399 2

並んだデータと逆順のデータでは、先頭を基準にすると 79800 回、深さ 400 段ですが、真ん中か 3 つの中央値にすると 2698 回、深さ 9 段に減ります。

全部が同じ値 7 のデータでは、どの基準でも 79800 回、深さ 400 段です。基準と同じ値がすべて「基準以上」の右の山に行くので、1 回分けても 1 個しか減りません。同じ値を別の山に集める 3分割 にすると、399 回、深さ 2 段で終わります。

真ん中や 3 つの中央値を基準にしても、その選び方を狙って作ったデータを渡されると、また偏ることがあります。選び方が決まっていれば、それを逆手に取る並びも作れるからです。

そこで、基準を乱数で選ぶ書き方があります。どの位置が基準になるかを前もって知る方法が無いので、狙って作った並びでも、毎回端の値ばかりを引くことはまず起きません。次のコードは、乱数の種 (乱数の出方を決める最初の値) を 1 に決めて、誰が動かしても同じ出力になるようにしています。仕事で使うときは種を決めません。

並んだ 3690 18
逆順 4438 24
全部同じ 79800 400

並んだデータで 3690 回、深さ 18 段、逆順で 4438 回、深さ 24 段になり、先頭を基準にした 79800 回から大きく減りました。それでも全部が同じ値のデータは 79800 回のままです。どれを基準に選んでも同じ値なので、乱数でも偏りは直らず、3分割 が要ります。実務の道具は、次の節の通り、最悪でも n log n の形で終わることを、決まりや作りで守っています。