Pythonでアルゴリズム「クイック・ソート」(１)：バスケットのアレ、覚えていますか？

こんにちは！本日は、Pythonでアルゴリズム・シリーズです！

今回は、「クイック・ソート」に取り組みます～。これまで、バブルソート、選択ソート、挿入ソート、シェルソートと、並び替えアルゴリズムを扱ってきましたが、これが最後で集大成！？です。

「クイックって、速いってことか？そのままだね～🤔」

はは、確かに。「速い並べ替え」ってことですね。でも、名前負けしていません。これまでご紹介したいなかで、もっとも処理速度が速いアルゴリズムです。

それだけに、ちょっと小難しい内容が含まれます。自分で自分を呼び出すという、再帰的な処理が登場するんです。（ちなみに、再帰関数については、過去の記事でご紹介しました。ぜひご覧ください！。）

もっとも速い（とされる）ソート・アルゴリズム、なんだか楽しみになってきましたよ～😆。

でも、いきなりコードから取り組むと迷子になるので、やはり、というか定番ですが、絵にしてまずはソートの手順の感覚をつかみましょう！

クイックソートって何だろう？

クイックソートのイメージは次の通りです。まず、「基準となる値」を決めます。これを「ピボット」と呼びます。

「バスケットで片足を固定して回転するアレか？😄」

あ、そうですね。pivotです。「回転軸」という意味です。ピボットを軸にして、その左右にある数字が回転して移動するイメージです。ピボットの左側に小さい数値を、右側に大きな数値を集めます。

それが終わったら、そのピボットの左右の数値を、それぞれグループと見立てて新しいピボットを決めます。そして同様の処理を続けます。そうすれば、いずれソートが完了するでしょう、というやり方です。

「やっぱり、言葉じゃ分かりません😭。

ですよね。そうだ、絵で紹介するんだった。絵で動きを追っかけてみましょう。

数値の移動が最小限

今、次のような9つの数値をソートしたいとします。運悪く、小さい数値が右に偏りがちな面倒くさそうな並び順です。

ここで、ピボットを決めます。真ん中の数値（要素数が偶数なら左寄りの数値）にします。そこを軸にして、左右の数値が移動します！

左側の数値のうち、ピボットより大きな値は右側へ、また右側の数値のうち、ピボットより小さい値は左側へ移動するのです。値を右に少しずつ詰める「バブルソート」「挿入ソート」のような無駄な動きがありませんね。

すると、次のようになります。左右のグループの並びとは無関係に、ピボットだった値が収まるべき場所は確定します。これだけでもだいぶソート完成に近づいた気がします。

続いて、左側のグループと右側のグループでそれぞれピポットを設定します。やはり、同様に、ピボットより大きな値は右側へ、また右側の数値のうち、ピボットより小さい値は左側へ移動します。

結果は、こうなります。ゴールが見えてきましたね！

さらに左右のグループでピボットを作って、数値の入れ替えを行います。右側のグループは数値の移動がないようです。

最後は、まとめて次のようになります。

おお、並べ替えが完成しましたね～。感覚的には、シェルソートよりも分かりやすいな気がします（個人的な感想です😅）。

ということで、クイックソートがどんなものか感覚を掴んでいただけましたでしょうか。今回もお絵描きがんばりましたよ～😉。

次回からコードを少しずつ見ていくことにしましょう！

では、ビーダゼーン！

※私のやる気アップとブログの品質向上につながりますので、記事が気に入られた方は、「ポチっ」と好きボタンを押してくださったり、フォローいただけますと幸いです🙇。