「本当はむずかしいクイックソート」解説

問題(?): http://d.hatena.ne.jp/sumii/20090722/p2

いきなり補足ですが、コメントでも指摘（ネタバレ？）されたとおり、一口に「クイックソート」と言っても（特にpartitionの）具体的実装は様々なバリエーションがあります。例えばホーアのオリジナルは、大まかに言っても

a[left]がpivotより大きくなるまでleft++する。ただしleftがaの範囲をオーバーしそうになったら中断して2にgotoする。
a[right]がpivotより小さくなるまでright--する。ただしrightがaの範囲をオーバーしそうになったら中断して3にgotoする。
leftがrightより小さかったらa[left]とa[right]を交換し、left++とright--をしてから、1にgotoする。
必要な場合はpivot要素を適切な位置に移動する（ミニクイズ：どのような場合にどこへ移動すればよいでしょうか？）

という感じで、決してシンプルではありません。Jon BentleyのProgramming Pearls（日本語訳「珠玉のプログラミング」）にも

Most discussions of Quicksort use a partitioning scheme based on two approaching indices like the one described in Problem 3. Although the basic idea of that scheme is straightforward, I have always found the details tricky---I once spent the better part of two days chasing down a bug hiding in a short partitioning loop. A reader of a preliminary draft complained that the standard two-index method is in fact simpler than Lomuto's, and sketched some code to make his point; I stopped looking after I found two bugs.

とありました（本は持っていないのでCACMの連載記事から引用）。要するに「（Hoareの）partition難しい」ということです。

さらに、アルゴリズムに関する標準的教科書の一つであるIntroduction to Algorithms（いわゆるCLRS）や、現時点の英語版Wikipediaには、（とりあえずa[0]をpivotとすると）次のようなpartitionアルゴリズムが載っています。

  pivot = a[0];
  s = 1;
  for (i = 1; i < n; i++) {
    if (a[i] <= pivot) {
      tmp = a[i];
      a[i] = a[s];
      a[s] = tmp;
      s++;
    }
  }
  tmp = a[0];
  a[0] = a[s - 1];
  a[s - 1] = tmp;

これはLomutoのpartitionと呼ばれることがあるようです（指摘感謝）。上述のProgramming Pearlsの

To partition the array around the value T we'll use a simple scheme that I learned from Nico Lomuto of Alsys, Inc.

が由来のようですが、そのLomutoという人が最初に（ないし自分で）考えたのかどうかはわかりませんでした。

（以下「後で書く」）

遅いにもほどがありますが（一年以上？）、とある授業のレポート課題の解説も兼ねて書きました（「詳しい説明」から下の部分）。