Pythonでアルゴリズム「シェル・ソート」(2)：グループごとにソートすれば計算量が減るのだ

こんにちは！では、「シェルソート」の続きです。最初からコードと向き合うのではなく、今回のソート・アルゴリズムについても、まずはイメージをしっかりつかんでおきましょう！

ということで、皆さんのためにせっせとお絵描きをしました。これで、なんとなく、でも確実に「シェルソート」の雰囲気を感じていいただけます。そして、コードの理解が容易になります。

「本当かいな！？🤔」

う、はい、頑張ります😅。確かに、これまで紹介したバブルソート、選択ソートなどに比べると、シェルソートは小難しいのです。

気合いを入れていきますよ～。

シェルソートは、挿入ソートの発展版

前回記事で、シェルソートは、「挿入ソート」の発展版である、という話をしました。リスト全体に「挿入ソート」を行ってしまうと、計算量が増えすぎてしまうことがあるんです。リストの要素のうち、小さい値が末尾側に偏っているときに昇順にソートしようとする場合がそうです。

これを回避するのが、シェルソートです。具体的には、並び替え対象のリストを何回かグループ化して「挿入ソート」を行います。はい、すでによく分からなくなってきましたね。

間隔４つで挿入ソート

下の画像をご覧ください。要素８つで構成されるリストを４つにグループ化したところです。

4つ間隔で要素がグループ化されていることが分かります。この４つに対してそれぞればに対して何をすると思いますか？そう、「挿入ソート」です。

「各グループに並べ替える数値が２つしかないけど、挿入ソートするの？🤔」

ええ。実際にやると、次の通りです。

「おお！小さい数値が、リストの末尾側に偏っていましたが、ちょっと先頭側へ移動しましたね！🙂」

そうなんです。長いリストの末尾側から先頭側へ挿入するために、大量に数値を右に一つずつ移動するという処理を回避できるんです！

間隔２つで挿入ソート

仕組みが見えてきましたね！でも、まだリスト全体はソートされていません。次は、リストの間隔をさらに半分、すなわち２つにしてソートします。

まずは、次の通り2つ間隔でグループ化します。

これをグループごとに挿入ソートで並べ替えます。結果は、次の通りです。

はい、これで間隔２のグループのソートもできました。

間隔１つで挿入ソート

間隔２つで挿入ソートを行ったことにより、要素の並びは次のとおりになりました。どうです？だいぶ昇順に近くなりましたね！

そして最後に、間隔１でグループ化して挿入ソートを行います！というか、要するに、基本の挿入ソートということですね。結果は、次の通りです。

無事ソートできました！

ところで、間隔がループの都度、２分の１になっていることはお気づきですね。この要素の間隔を決めるには、いくつかの方法が提案されているようですが、一番単純な要素の半分から始めて、以降ループごとにどんどん半分にしていく方法を採用しています。これが最も効率がいいとは必ずしも言えないらしいですが、ここでは深く追求するのは、やめておきましょう。

次回は、上記のようなざっくりとした概念図ではなく、紹介予定のコードに沿った数値の動きを丁寧に解説したいと思います。

では、ビーダゼーン！

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