#1. はじめに

皆さんおなじみのクイックソートを実装する機会があり、
クイックソートの平均時間計算量がなぜ$O(nlogn)$なのか気になってしまいました。

本稿では、平均時間計算量に加えて、
初期配列が最悪の場合と最良の場合の時間計算量の求め方もまとめようと思います。
勉強中なので、タイトルに（メモ）と記載してます。
間違っていたらご指摘いただけますと幸いです。

#2. そもそもクイックソートって？
クイックソートは、実用上、内部ソートの中で一番高速なソートアルゴリズムです。

このアルゴリズムでは、まず、初期配列の要素から基準値（pivot）を選び、
pivot以下かより大きいかで配列の要素を二分割します。

そうすると、昇順に並べる場合、
[pivot以下の値である配列要素] [pivot] [pivotより大きい値の配列要素]
の順に初期配列を並べ替えることができます。

pivot以下の値の（又はpivotより値の大きい）グループの中では、整列がまだ完了していないので、
それぞれのグループにおいて、新たなpivotを選び、同様の分割を繰り返します。
実際にプログラムを書く上では、この分割の処理を再帰的に呼び出すようにします。

分割を繰り返したのち、
配列の要素を要素数$1$のグループまでバラバラにできたら、
配列の整列が完了します。

どれほど効率よく配列をバラバラにできるかで、
$O(n^2)$（最悪）から$O(nlogn)$（最良）まで時間計算量が違ってきます。

#3. 最悪時の時間計算量
最も非効率に分割が進むケースは、
pivotを除く$n-1$個の要素を$n-1$個と$0$個に分割する過程が最後まで続くケースです¹。

この時の分割に必要な比較回数を漸化式で評価してみましょう。
$T_n$をサイズ$n$の配列を整列するのに必要な比較回数とします。

漸化式は、

T_n = n-1 + T_{n-1} \quad ( n \geq 2)

であり、これを解くことで$T_n$のオーダーは、

\begin{eqnarray}
T_n &=& n-1 + n-2 + ・・・ + 1 \quad \left(\because T_1 = 0 \right) \\
　　&=& \frac{n \times (n-1)}{2} \quad ( n \geq 2)
 \\
　　&\rightarrow& O(n^2) 
\end{eqnarray}

と求まります。

配列を整列するためには、要素の比較以外に要素の交換も必要となりますが、
その手数は比較回数の定数倍以下なので、オーダーだけ考える場合は特に気にしなくてよいです。

#4. 最良時の時間計算量
次に、最も効率的に分割が進むケースを考えましょう。
最悪時は、分割の仕方に極度に偏りが生まれることで、
一方のグループのサイズは分割前と同程度の大きさになるため、分割が進んでいませんでした。
最良の分割が行われるには、均等に分割が進むことが重要です。

簡単のために、サイズ$n$が$2^k$である配列が二分割されていく状況を考えてみましょう。

一つの配列要素に注目したときに、
その要素の位置を確定させるまでに必要な分割回数は、大雑把に$k$回です。
厳密に言えば、分割回数分だけpivotが生じて、
pivotに選ばれた要素の位置が確定するイベントが起きるので、
分割回数は$k$より小さくなりえます。
しかし、$k$が大きいとき$n >> k$であるため、
pivotの生成回数は配列サイズ$n$に比べ十分小さくなります。
そのため、オーダーの計算ではpivotの寄与を無視することにします。

言葉だけの説明なので少々わかりにくいですが、
大事なことは、どの配列の要素に関しても、位置を確定させるために、
$k$回の分割過程を要するということです。

分割回数がわかったので、分割前に行う要素の比較回数を求めます。
要素数$m$のあるグループを持ってきた際、その中での要素の比較回数は $m-1$ です。

ですので、
分割が$1$回進み、要素数$2^{k-1}$のグループが$2$つ存在する状況では、
$2$回目の分割を進めるために、

2(2^{k-1}-1) = n - 2 \sim n

と$O(n)$回の要素の比較が必要です。
この計算を同様に、$3回目、4回目・・・k回目$の分割を進める場合についても行うと、
どの場合も比較回数は$O(n)$になることがわかります。

それゆえ、配列が二分割されながらソートが進む場合、
その時間計算量は

O(nk) = O(n \log n) \quad \because (k = \log n)

になります。

#5. 平均時間計算量
最後に、平均時間計算量を求めましょう。

平均時間計算量を解析的に求めるために、ある条件を設定します。
全分割工程であらゆる分割パターンが等確率で生じるという条件です。
つまり、サイズ$n$の配列であれば、$(0,n-1)、(1,n-2)、・・・(n-1,0)$への分割が等確率で起こるということです（$(L,R)$において、$L,R$は分割後のグループの要素数）。

初期配列がランダムである状況、または、初期配列に偏りがあるもののpivotの取り方がランダムである状況が、この条件を成立させてくれます。

比較回数に関して、漸化式を立てて考えてみます。

\begin{eqnarray}
T_n &=& n-1 + \frac{1}{n} \sum_{k=1}^{n} \left( T_{k-1} + T_{n-k} \right) \quad (n \geq 2) \\ 
　　&=& n-1 + \frac{2}{n} \sum_{k=1}^{n} T_{k-1} \quad (n \geq 2) \\
\end{eqnarray}

これを$T_n$について解くためには、ちょっとした工夫が必要です。

S_n \equiv T_n - 2

と定義します。$ n \geq 2 $において、

\begin{eqnarray}
nT_n = n S_n + 2n &=& n(n-1) + 2 \sum_{k=1}^{n} (S_{k-1}+2) \\
　　　&=& n(n-1) + 2 \sum_{k=1}^{n} S_{k-1}  + 4n
\end{eqnarray}

なので、

nS_n = n(n+1) + 2 \sum_{k=1}^{n} S_{k-1} \quad (n \geq 2)

が成り立ちます。

この式の和記号の部分を処理するために、$nS_n - (n-1)S_{n-1}$という差分を取ると、

nS_n - (n+1)S_{n-1} = 2n \quad (n \geq 3)

という関係が求まります。この両辺を$n(n+1)$で割ると、

\frac{S_n}{n+1} -\frac{S_{n-1}}{n} = \frac{2}{n+1} \quad (n \geq 3)

になり、$n = 3$になるまで$n$を減らして両辺を足し合わせると、

\frac{S_n}{n+1} -\frac{S_{2}}{3} = \frac{2}{n+1} + \frac{2}{n} + ・・・+ \frac{2}{4} \quad (n \geq 3)

ゆえに、

\frac{S_n}{n+1} = 2 \left( \frac{1}{n+1} + \frac{1}{n} + ・・・+ \frac{1}{2} + \frac{1}{1} \right) -2 \left( \frac{1}{3} + \frac{1}{2} + \frac{1}{1} \right) + \frac{S_{2}}{3} \quad (n \geq 3)

が成立します。

右辺第一行は調和数と呼ばれ$\log n$で近似できるため、

\begin{eqnarray}
S_n & \sim & 2 (n+1) \log n + C(n+1) \quad (n \geq 3 \ \& \ C =  const) \\
\therefore T_n &\rightarrow & O(n \log n) 
\end{eqnarray}

と平均時間計算量を求めることができました。

$n=1,2$の場合を取り扱っていませんが、今は計算量のオーダーを考えているので、
$n \geq 3$の場合で計算量を求めるだけでよいです。

6. おわりに

クイックソートの時間計算量についてまとめました。
自信がない点もあるので、間違い等あればご指摘いただければと思います。
今後は、マージソートやヒープソートなど他の有名ソートについても勉強して、
クイックソートと比較したいと考えています。

7. 参考

「クイックソートの計算量は、ピボットの選び方に依存します。もし最大限に偏った非常に悪いピボットの選び方をすると計算時間は $O(n^2)$ になります。例えばピボットによる左右分割が、常に片方が 0 個でもう片方にすべて偏った場合には計算時間が $O(n^2)$ になります。　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　反対に常に分割が左右均等に分かれていれば、計算時間は $O(nlogn)$ になります。そればかりか実は少々偏らせる程度では $O(n^2)$ にはならず、例えば分割が毎回 1:99 に分かれるとしても、1:99 で不変である限りは計算時間は $O(nlogn)$ になります (ここはよく誤解されがちです)。」この記述を理解していきたい。 Ref(参考1) ↩