Version 13.15
最速・クイックソート

「前回まではソートの中のバリエーションを見てみたけど、今回からは話を
戻して、色々な種類のソートについて見ていきます」
『そういえばバブルソートって一番時間掛かるんだったんだもんね』
「そう、だからバブルソートはまず使いません。そこで、実際に使うソート
について説明します」
『おー』
「まずは【クイックソート】から」
『クイック、って速そう』
「その名の通り最速のソートです」
『なんだ、これ使えばいいんじゃん』
「でも安定ソートじゃないんです」
『げ！』
「なので、安定ソートじゃなくていい場合にはクイックソート、安定ソート
したい場合には、今度説明する【マージソート】というものを使います」
『使い分けするってこと？』
「でもマージソートもかなり速いから、全部マージソートでしてもいいかも
ね」
『じゃあクイックソート意味ないじゃん……』
「でも知名度的にはクイックソートの方が上だから、これは憶えておかない
と」
『はーい』
「まず、クイックソートの基本的な考え方は〈分割〉」
『分割？　分けるってこと？』
「そう、ある数字より、小さければ左、大きければ右っていうふうにデータ
を分けて、それをどんどん繰り返すっていう方法。たとえば」

4 9 3 5 8 

『前と同じ数字ね』
「まず、適当な数――ここでは真ん中にある数、 3 ってするけど、この数
を決めて、この数より小さい数は左に、大きい数は右に持って行きます」
『左に小さいの、右に大きいの、ね』
「このときの方法はこんな感じ。まず、左から見ていって 3 以上の数
があったら止まります。最初の 4 がもう 3 以上だからそこで止まります」

4 9 3 5 8 
^

「次に、右から見ていって、 3 以下の数があったら止まります」

4 9 3 5 8 
^   ~←

「そうしたらこのふたつを入れ替えます」

3 9 4 5 8 
^   ~

「それを繰り返します。まず ^ を右に進めて 3 以上の数を探します」

3 9 4 5 8 
→^ ~


「次に ~ を左に進めて 3 以下の数を探します」
3 9 4 5 8 
~ ^

『あ、 ^ と ~ がすれ違った』
「両方とも止まったときに、位置が入れ替わっていたら、１周目は終了。こ
のとき、 ^ と ~ の間は小さい数と大きい数の境界線になります」
『？　なんで？』
「すれ違った、ってことは、 ^ から見ると〈すでに ~ が入れ替えた数〉を
置いてきた所まで進んだってこと。つまり ~ が右から持ってきた小さい数
を置いてある場所、の右端」
『確かに左端から 3 までが ~ が置いてきた小さい数、ってわけね』
「そういうこと。この交差位置の、左には 3 以下の数、右には 3 以上の数
が来てるでしょ」
『ん？　イコールは？　3 は左に来ちゃってるけど』
「このアルゴリズムは = は両方とも含むから」
『 = だととにかく交換しちゃうわけね』
「そういうこと。クイックソートは左右ごちゃごちゃと入れ替えるから」
『安定ソートにならないわけね……』
「さて、話を戻して」

3 9 4 5 8 
~ ^

「ここから２周目。この交差した位置を中心に、ふたつに分けます」

3        9 4 5 8 

「次に、それぞれ、さっきと同じことをします」
『左右から見ていって入れ替え？』
「そういうこと。まず左側」

3        9 4 5 8 

「と、こういうふうにひとつだけになった場合には、何もしません」
『ソートのしようがないものね』
「次に右側」

3        9 4 5 8 
         ^     ~

「から初めます。まず真ん中の数――ここでは左側の 4 を使って、まず ^ 
を、 4 以上の数まで移動します」
『って、移動しないね』
「そういうこと。次に右の ~ を、 4 以下まで移動します」

3        9 4 5 8 
         ^ ~ ←

「というわけで交換します」

3        4 9 5 8 
         ^ ~

「同じように、左から 4 以上を探します」

3        4 9 5 8 
         →^
           ~

「右から 4 以下を探します」

3        4 9 5 8 
           ^
         ~←

『交差したからここまでね』
「で、ここでまた分割」

3        4        9 5 8 

『また分けるのね』
「そういうこと。同じく、左側は 4 だけだからソートしません。というわ
けで右側」

3        4        9 5 8 
                  ^   ~

『真ん中の数字は 5 ね』
「まず ^ は、 5 以上の数ということで動きません。 ~ は 5 以下の数とい
うことで 5 で止まります」

3        4        9 5 8 
                  ^ ~←

「そして交換」

3        4        5 9 8 
                  ^ ~

「次は交差します」

3        4        5 9 8 
                  ~ ^

『分割ね』

3        4        5       9 8 

「同じく左側は 5 だけだからソートしません。というわけで右側」

3        4        5       9 8 
                          ^ ~

『これの入れ替えね』

3        4        5       8 9

「これでソート完了」

3 4 5 8 9

『おー、ちゃんとソートされてる！！』
「まぁ、今のはうまくない例だけど、うまくいけば半分ずつくらいに分割し
ていきます」
『そだね、今回のだと左からひとつずつ取っていく感じ……』
「実はクイックソートの弱点はそれ。クイックソートは、データの並び方に
よってはかなり非効率なんです」
『むむむ、なんかクイックソートって良くないことばかりのような』
「でもデータによっては効率的に分割できるから。その辺がクイックソート
の方が早い理由かな」
『んー、ぱっと見、よくわからないかも……』
「ま、ちゃんとした〈早さ〉についてはもう少しあとで説明するから。それ
と、今は【中央の値】を【真ん中の値】ってしていたけど、これも別の方法
があるから」
『別の方法？』
「全部の平均取ること」
『……つまり、全部足して、個数で割る？』
「そういうこと」
『その方が時間かかりそう……』
「ということもあって今回はしなかったけど、そういう方法もあるってこと
で。さて、まとめると、クイックソートには以下のような特徴があります」

・「入れ替えて分割」の繰り返し。
・基本的に最速。でもデータによりばらつきがある。
・安定ソートではない。

『バブルソートと一長一短って感じね』
「結局、クイックソートは使わないことが多いと思うけど、でも仕組みは
ちゃんと理解しておいてね」
『はーい』

/*
    Preview Next Story!
*/
『ぷらとわって、使わないけど教える、っていうの多いよね』
「仕組みを説明するためには、そういうことも必要だから」
『でも、それがあるからどんどん伸びるのよねー』
「う”」
『最近、１講座半年ペースだし……』
「というわけで次回」
＜ Version 13.16 クイックソートのコーディング ＞
『につづく！』
「でも、他も使わないこと教えると思うよ」
『え、そうなの？』
「ただ〈使えない〉ことを教えないだけだと思う」
『……』