ネタ元>再帰をループに変換
クイックソートとは以下の順序でソートを行うものです。
(1)ある要素を取り出し、その要素より小さいグループと大きいグループで分類する
(2)それぞれのグループに対し、要素の数が1個になるまで(1)を繰り返す
このクイックソートが必要とするメモリ量、すなわち空間計算量を考えてみましょう。
要素を2つに分割した後、両方を同時に処理することはできません。
ですから、一方はいったん置いて他方を処理します。
その処理中にまた2つに分割されるため、いったん置いたうえにさらに置くことになります。
図で表現するとこんな感じですね。
このようにうまく二等分できれば一時領域は10段もあれば十分です。
この一時領域をスタックサイズと呼びます。
別の場合のスタックサイズを考えてみます。
こんな場合はどうでしょうか。
先ほどと違い、うまく分割することが出ていません。
そして、このペースだとスタックサイズは500段必要です。
一体スタックサイズは何段用意しておけばいいのでしょうか。
出来るだけスタックサイズを小さくする方法を考えてみます。
このスタックは処理中のものが終了するまで積まれ続けるわけです。
いつ終了するんでしょうか。
それは、処理中の要素数が2個以下になるまでです。
それならば、早く処理中の要素数を減らせばよいわけです。
2つに分割したとき、どちらをスタックに積み、どちらを処理中にするかは
自由に決められるため、要素が多い方をスタックに積んでしまえばいいのです。
それを図示しました。
いずれも4:1のグループに分かれていますが、左の方はもうすぐ処理が終わりそうです。
このように、アンバランスに別れた方がスタックに積む量が減るため、
最もスタックが必要なパターンは二等分されるパターンです。
そして、二等分された場合、スタックサイズはlog2(N)必要です。
よって、クイックソートの空間計算量は最悪の場合でもO(logN)です。
なお、ピボットに使われた要素は処理済みにするのが好ましいため、
1000個は499個＋1個＋500個のように3つに分けられますが
今回は分かりやすくするため、それを無視しています。