やっぱり研究というほどじゃないけど
以前似たようなタイトルの日記を書いたが、今回は用語ではなくアルゴリズムの話。*1
クイックソートという名前なのだが、アルゴリズムを少し勉強した方なら誰もが聞いたことがあるだろう。
厳密に説明するのは面倒なのでここでは適当に説明するが、
数字の列（数字に限らないが、単純化のために数字とする）を与えられたとき、
１：列から一つ、基準を持ってくる。
２：（非常に大雑把には）基準より大きいものと小さいものに分ける。
３：それぞれに再び１から適用、列の中身が一つの時点で１を適用したら終了する。
という感じのアルゴリズムである。
特徴として速いことが挙げられる*2。
あとは、安定でない。同じ数字（と見なされるもの）があった場合、その順番が元の列の順番を保存しない。
主に２で分けるときに、partitionというアルゴリズムで分けるためである。
大雑把には、
１：列の中から基準を一つとる。
２：基準より大きいものを列の左から、小さいものを右から探し、最初に出てきたそれぞれを入れ替える。
３：２を繰り返して、「大きいもののある位置」が「小さいもののある位置」より右側にきたら、最後に大小の境界部分に基準を置いて終了。
という作業である。
まあ、入れ替えたりするんだから、前後関係は変わったりしそうだなあ、と思ってもらえれば十分である。
で、わざわざ書く理由は何かというと、明らかに安定な「クイックソート」があるからだ。
いや、これをクイックソートと呼んでいいのか私には判断しかねるが*3。
で、具体的にはどうするかというと、partitionに当たる部分が
１：列の先頭の一つを基準にする。
２：次の要素が基準より小さければ「左」の列に、基準より大きければ「右」の列に追加する。
３：列の最後まで２を繰り返し、最後までみたら「左」の列と「右」の列が「分けたもの」である。
というもの。
元のアルゴリズムと比べると、
１：列が余計に増えている（再利用していない）
２：入れ替えじゃないので、位置関係の張り替えが二回行われている
３：安定である*4
という点が異なる。
これ、速いのだろうか・・・？（遅いとは思わないが、操作が増えている気がする）
ちなみに、このアルゴリズムが書かれるのは、Haskell（代入が制限されている）などの関数型言語（の一部）やProlog（代入という概念がない）などの論理型言語である。
良い悪いをここで議論する気はほとんどないが、「わずか〜行で（こんなに簡単に）クイックソートがかけます！」というのはさすがに誇大広告のような気がしてならない。
柔軟性を主張しようにも、そんな型にはまったアルゴリズムを一から書く人間はほとんどいないのだから。
