Pythonでアルゴリズム「挿入ソート」（１）：順番に右に詰めてください～♪

今回は、Pythonでアルゴリズムシリーズ！の中でも「挿入ソート」を扱います～。

「これでソートのアルゴリズム3つ目ですね～🙂」

そうなんです。「バブルソート」、「選択ソート」に続いて、早くも3つ目なんですが、まだまだあるんですよね…。そして、この「挿入ソート」はその中でも、基本の部類に入るのです！

よし、この「挿入ソート」も身に付けたるで～、と気合が入ってきましたよ（私だけ😅）。

挿入ソートの特徴

詳細に入る前に、この整列（ソート）のイメージを掴みましょう。めあては、数字を「昇順に並べる」ことです。未整列の数字カードを取り出しては、小さい順に並べることによってソートを完了させます。

分かりにくい😭？では、もう少し具体的にしましょう。

数字のカード5枚がバラバラに存在します。まず、そのカード達から1枚だけ取り出します。「９」でした。そのカードをそっと別の場所に置きます。これが初期状態です。そして、「９」は整列完了です。

つづいて、もう１枚をカード達から取り出します。「６」でした。「９」より小さいです。「９」をちょっと右にずらして、空いた場所に「６」を置きました。「６」「９」は、整列完了です。

さらに、1枚カードを取り出しました。「１０」です。整列済みの一番右にある「９」よりも大きいです。「９」の右に「１０」を置きました。「６」「９」「１０」は整列完了です。

次のカードは、「８」でした。「１０」を右にずらし、さらに「９」も身に右にずらしました。しかし、「６」は、「８」より小さいのでずらしません。空いたところにの「８」を置きました。「６」「８」「９」「１０」は整列完了です。

最後のカードは「７」です。「８」「９」「１０」のカードを右にずらして空いたところに、「７」を置けば、「６」「７」「８」「９」「１０」となり、すべて整列完了です。

と、ここまで書きましたが、まだ分かりにくい！！文章で表現するのにも限度がありますな…😭。やっぱり絵にしましょう、絵に。

ポイントは、挿入したい値よりも大きい値は、右に右に１つずつずらしていくところです。

「整列済」vs「未整列」で数字を分ける

よし、今度こそ、挿入ソートのイメージを掴みますよ、絵を使って！（結構、描くのが大変なんですよ😅）。

１．数値を準備

まず、未整列の数値を5つ準備します。見事に未整列です…。これらの数値を昇順に並べたい！果たしてどうする？

２．「整列済」と「未整列」の値に分ける

まず、これらの数字のうち、左端を「整列済」として、残りは「未整列」とします。

「なんの整列作業もしていないのに、整列済み！？🤔」

整列対象が一つ「９」しかないから、整列済みなんですよ～（多分ね）。

３．未整列の左端の値を取り出して保存

続いて、未整列の値のうち、左端の値を取り出します。これがカードを取り出したところですね～。tmpという箱にでも入れておきましょう。

この引き抜いた値を、整列済みの値の正しい場所に挿入したいんです。そして、未整列の値のうち、左端に空きスペースができましたね。ここがミソです。

４．挿入したい値より大きいなら右に詰めてください！

では、整列済みの値の右端からtmpの値を大きさ比べをします。tmpより大きいですか？なら、その数字は邪魔ですね。

じゃあ、右に詰めていただきましょう。すると、今度はそこに空きスペースができます。病院の順番待ちか😅！？さきほどスペースを作っておいたのでこれができるわけです😆。

５．空いたところにｔｍｐを挿入

早くも整列済みの数値の比較が終わってしまいました。一つしかなかったので。じゃあ、空いたところにtmpの値を入れましょう。

６．整列1回目完了！

はい、これで６と９の２つの数字は、整列できました。これにより、整列済みのエリアが一つ分広がりましたね。

きっと、これを繰り返していけば、5つの数字の整列が出来上がるはずだ～、と直感したところで、今日はここまで。

では、ビーダゼーン！

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