ノート:クイックソート

アルゴリズムと実行例の対応

アルゴリズムと実行例が繋がらないんですが --以上の署名の無いコメントは、61.7.2.217（会話）さんが 2006-03-20T12:33:25 に投稿したものです（Glayhours（会話）による付記）。

実装例の空間計算量の注記について

「ただし、これはよくあるダメな実装の例である。」以降の説明がよく理解できないのですが、私だけでしょうか。"quicksort(a, left, i - 1);"と"quicksort(a, j + 1, right);"の呼び出し順を工夫することで、最大の再帰深さを抑えられるという主張に見えますが、呼び出し順を変えたところで変わらないと思いますが如何でしょうか。--Fujikaks（会話） 2021年7月23日 (金) 15:33 (UTC)[返信]
- 私もその記述を気にしていて、できれば修正したいと考えていた所ですが、先に他の方が修正してくださったのでノートで補足します。
  クイックソートが最悪計算時間（O(n^2)）になるのは、たとえば100要素が99:1、分割した99要素が98:1……と偏って分割されていく時です。
  この際、素朴に前の要素から再帰させていくと、
  99を先に処理して1をスタックにpushする→98を先に処理して1をスタックにpushする→97を……となり、すべての「残り1」がひたすらスタックに積まれていきます。この時、空間計算量＝スタックは要素数に比例するため、O(n)となってしまいます。
  一方で、要素数が小さい方を先に呼び出すようにすると、
  99をスタックにpushして、後半の1を先に処理する。後半は1要素しかないのでソート完了。99をスタックからpopする。
  →popした99の中で、98をスタックにpushして、後半の1を……となり、「スタックに積まれた要素が、次のステップで必ず解放される」状態となります。
  このように実装すると、「最もスタックを消費するのは、常に均等に分割された時＝計算時間が最良の時」という形になり、空間計算量を最悪でもO(logn)オーダーに低減できます。
  （クイックソートの発明者であるC.A.R.ホーア自身の論文に記されているようです）追記：こちらのP11にありました。"in order to ensure that the number of segments..."以降の記述です。--Linearithmic（会話） 2021年8月3日 (火) 10:10 (UTC)[返信]
  たとえばCの場合、再帰ではなく、スタックを自力で実装してループ化することで明示的にO(logn)スタックを保証できます。この辺りは各言語の仕様によると思われます。--Linearithmic（会話） 2021年8月2日 (月) 14:15 (UTC)[返信]
  - ありがとうございます、理解できました。空間計算量の節が若干修正されたようなのですが、下の実装例が再帰を使ってるのに、自前でスタックを用意した場合の計算量が書かれているのが混乱のもとなんですかね。再帰が使用するコールスタックと、自力で用意するスタックを混同しているようにも見えて、特に最後あたりの記述は誤りにも見えます。再帰を使う場合はコールスタックの消費として最悪 $\mathrm {O} (n)$ (パーティションが偏った場合)、再帰を使わずに処理順を管理するスタックを用意した場合には小さい側を先に処理する工夫をすることで最悪 $\mathrm {O} (\log n)$ (パーティションが均等だった場合)に抑えられるという書き方がよさそうですがいかがでしょうか。--Fujikaks（会話） 2021年8月7日 (土) 04:41 (UTC)[返信]
  - ご指摘ありがとうございます。おっしゃる通り、再帰と非再帰で分けて書ければ一番わかりやすいのですが……再帰を使う場合でも、末尾再帰の最適化がサポートされている場合、「要素数が少ない方を普通の再帰に、要素数が多い方を末尾再帰に回す」ことでコールスタック視点でもlogn空間にできるようなんですね（英語版で、Sedgewickを引用元にそう書かれていた）。「言語の仕様による」とか、かなり濁した書き方にしてしまったのはそのためです。正直関数型には明るくない……あとCの実装例も時間さえあれば非再帰版付けたいです。注釈のサイトを参考に。末尾再帰にまで手を出すとアルゴリズムの解説としては煩雑になる（のと、個別の言語に言及しないと動作を保証できない）ので、
    「再帰を使わず、分割された範囲をスタックで管理することでループ化し、要素数の少ない方を先に処理する」といった、最悪空間計算量を $\mathrm {O} (\log n)$ に抑えられる実装方法がある。
    ぐらいが現状一番無難かなあ、と考えています。--Linearithmic（会話） 2021年8月7日 (土) 16:00 (UTC)[返信]

Pythonの実装例の不備について

入力が[1, 4, 2, 3]のときに出力が[1, 3, 2, 4]になります。 --Pocomaru（会話） 2021年10月14日 (木) 05:06 (UTC)[返信]