Pythonでアルゴリズム「シェル・ソート」(1)：ひと工夫で「挿入ソート」が加速する

こんにちは！今回は、Pythonでアルゴリズムを学ぼうという企画の続編です。取り上げるのは、並べ替えアルゴリズムの一つ「シェル・ソート」です。

「挿入ソートの進化版」とでもいうべきものであり、単純な「挿入ソート」よりも高速で並べ替えが可能になります。

「シェルの意味って『貝殻』（Shell）の意味ですか？🤔」

いや、人物の名前です。このアルゴリズムを考え出したドナルド・シェルさんの姓に由来します。「タバタ・トレーニング」「ヤマナカ・ファクター」みたいに開発・発見した人物の名前が学術用語になることがありますが、それですね。

ということで、シェルさんが1959年に発表した、このアルゴリズム、何か凄そうですね。ぜひ学んでみましょう！

リスト全体への挿入ソートは計算量が多すぎる

先ほど、触れたようにシェル・ソートは、「挿入ソートの進化版」です。では、リスト全体に対して単なる挿入ソートを行うと何が欠点なのでしょうか。まずはそこから確認しましょう。

仮に、１～８の数値で構成される次のリストを、「挿入ソート」で昇順に並べ替えるとします。注目してほしいのは、右側に小さい数字が（偶然）少し偏っていることです。

挿入ソートの処理が始まってしばらくすると、次の画像のような状態になります。左側に整列済みの数値が、右側に未整列の数値があります。

次のループで5番の値「３」を整列済みエリアに挿入します。

整列済みエリアにあるすべての値と比べた結果、「３」は最も小さかったので、一番左に入ることになります。

「３」が入る場所を作るために、４～８の皆さんは、右側にひとつづつ移動します。つまり、整列済みエリアにあったすべての値は、「３」と比較され、右に移動することになりました。いや、これはなかなかコンピュータの処理量が多いですね。

さらに、次に挿入される値は、「１」ですね。同じように一番左に収まるためにたくさんの処理が必要になります。なんか、非効率な気がしませんか？

「どうせなら、小さい値がもっとリストの左側に偏っていればよかったのに😑」

ですよね。そこで、シェルソートの登場です。シェルソートでは、「挿入ソート」の計算量が効率的になるよう、グループ分けをして挿入ソートを繰り返します。この手順で、数値の偏りが少しずつ調整されます。

さて、どんな処理をするんでしょうね…。それは次回ご紹介しましょう。ということで、「シェルソートとは何か？」、その導入でした。

では、ビーダゼーン！

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