「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典

順番に見ていきましょう。
まずは予備知識として「ソート」について簡単に説明します。
「そんなの説明されなくても知ってるよ！」な人は適当に読み飛ばしてください。

ソートは「何らかの規則に従ってデータを並べること」です。
並べる順番は

・小さい順（昇順）
・大きい順（降順）
・アルファベット順
・五十音順
・古い順
・新しい順
・好きな順
・嫌いな順

など、いろいろ あります。



以上を踏まえて、本題に入ります。

データを小さい順（昇順）、もしくは大きい順（降順）に並べたいとしましょう。

いろいろな やり方があります。

その「いろいろな やり方」のひとつが「クイックソート」です。

クイックソートでやることは

１．基準値を決める
２．基準値より大きい値を基準値より右に置く
３．基準値より小さい値を基準値より左に置く

の3つだけです。
※左が「小」で右が「大」と仮定しています。

それを「基準値よりも大きいグループ」と「基準値よりも小さいグループ」に対して何回も繰り返すことで全体を並べ替えます。

……と言葉で説明されてもピンと来ないですよね。

大丈夫です。
例を挙げて説明します。

ここに「0」から「9」までの数字がバラバラにありました。
これをクイックソートで並べ替えます。



最初にやるのは基準値を決めることです。
今回は何となく「6」を基準値に決めました。



次に基準値の「6」よりも小さい数字を「6」の左に並べます。
「6」よりも大きい数字を「6」の右に並べます。



そうすると

１．基準値「6」より小さい数字のグループ
２．基準値「6」
３．基準値「6」より大きい数字のグループ

の3つに分類されます。



次に

１．基準値「6」より小さい数字のグループ
３．基準値「6」より大きい数字のグループ

に対して、同時に同じことをやります。

……が、一緒くたにして説明すると混乱するので順番にやってみましょう。
まずは基準値「6」より小さい数字のグループに着目します。



基準値「6」より小さい数字のグループの中にあるのは「0」から「5」までの数字です。
この中から基準値を決めます。

……そうですね。
「2」にしましょう。
「2」を基準値にします。



次に基準値の「2」よりも小さい数字を「2」の左に並べます。
「2」よりも大きい数字を「2」の右に並べます。



そうすると

１－１．基準値「2」より小さい数字のグループ
１－２．基準値「2」
１－３．基準値「2」より大きい数字のグループ

の3つに分類されます。



次に、基準値「6」より大きい数字のグループに着目してください。



基準値「6」より大きい数字のグループの中にあるのは「7」から「9」までの数字です。
この中から基準値を決めます。

……そうですね。
「9」にしましょう。
「9」を基準値にします。



次に基準値の「9」よりも小さい数字を「9」の左に並べます。
「9」よりも大きい数字を「9」の右に並べます。



そうすると

３－１．基準値「9」より小さい数字のグループ
３－２．基準値「9」
３－３．基準値「9」より大きい数字のグループ

の3つに分類されます。



ここまでを復習しておきましょう。

最初のグループ分けで

１．基準値「6」より小さい数字のグループ
２．基準値「6」
３．基準値「6」より大きい数字のグループ

の3つにグループ分けされました。



次のグループ分けで

１－１．基準値「2」より小さい数字のグループ
１－２．基準値「2」
１－３．基準値「2」より大きい数字のグループ
２．基準値「6」
３－１．基準値「9」より小さい数字のグループ
３－２．基準値「9」
３－３．基準値「9」より大きい数字のグループ

のようになりました。



あとは、これをグループ分けできなくなるまで繰り返すだけです。
最終的には、例えば以下のようになります。



おぉ、ちゃんと小さい順に並びましたね。



ここまでを振り返ってみて、いかがでしょうか。

やっていることは

１．基準値を決める
２．基準値より大きい値を基準値より右に置く
３．基準値より小さい値を基準値より左に置く

の3つだけですよね。
この3つを「もう、これ以上できないよ～！」となるまで繰り返しているだけです。

これがクイックソートの基本的な考え方です。

ちなみに、クイックソートは

基準値の収まる場所を確定させていく やり方

とも言えます。

先程の例を思い出してください。

基準値「6」でグループ分けした結果

１．基準値「6」の左に6個の数字
２．基準値「6」の右に3個の数字

になりましたよね。



最終的な並び順と比較してみましょう。
最終的な並び順でも

１．「6」の左に6個の数字
２．「6」の右に3個の数字

になっています。



そうです。
グループ分けした時点で、基準値は収まるべきところに収まっているのです。
「他の奴らは知らんけど、俺の場所はココだな！」になっています。



うまく基準値を決めて、うまくグループ分けをすると、複数の基準値の位置を同時に確定できます。
同時に位置を確定できる基準値の数が多いほど、全体の並べ替えが速くなる理屈です。

自分のイメージしやすい方で覚えてあげてください。
クイックソートは

「基準値より小さいグループ」「基準値」「基準値より大きいグループ」のグループ分けを、グループがなくなるまで繰り返すやり方

であり

基準値の収まる場所を確定させていく やり方

でもあります。



さて、ここまでを振り返ってみて、いかがでしょうか。
「あれ？思ったより難しくないのでは？」と感じてもらえたのであれば嬉しいです。

そうなのです。
クイックソートの考え方自体は、そこまで難しくありません。

ですが、実際の処理を見ると、ゴチャゴチャしていて複雑に感じると思います。

その理由は

１．基準値の決め方
２．グループ分けの仕方

に、あれやこれやの工夫を凝らそうとしているからです。

なんとなく分かると思いますが、基準値はグループ内で大きくもなく小さくもない値が理想です。
この「大きくもなく小さくもない値」を選ぶために、あれやこれやと工夫をしている場合があります。

これがクイックソートを難しく感じさせる理由その1です。

あと、グループ分けするときは、それぞれの数字の大小関係を比較して移動します。
この「大小関係を比較して移動」を効率的にやるために、あれやこれやと工夫をしている場合があるのです。

これがクイックソートを難しく感じさせる理由その2です。

クイックソートの「考え方」自体は、そこまで難しくありません。
ただし、考え方をしっかり理解していないのに「効率的なやり方」まで踏み込んでしまうと、すごい難しく感じると思います。

まずは、クイックソートの考え方を頑張って理解してください。
遠回りに感じるかもしれませんが、それが一番の近道です。