Pythonでアルゴリズム「シェル・ソート」(6)：取り出す、挿入する。それだけだ！

はい、こんにちは！本日も、やはりPythonでシェルソートの続きをやります！前回記事では、一番外側のループを解説しました。グループ化するときの要素の間隔をループの都度、2分の1にするのでしたね。

では、今回は、真ん中のループに取り組みます。実際に処理することは「挿入ソート」なわけですが、単純な「挿入ソート」と比べて小難しいです。

「やだな～😑。」

いやいや、丁寧に分析すればきっと分かるはず（と自分にも言い聞かせています😅）。さあ、「シェルソート」の「中ボス」、真ん中のループにジャンプ・イン！

「真ん中のループ」で挿入ソート！？

まず、コードの全体像を再掲します。今回取り組むのは、赤枠内、即ち、for文のブロックである「真ん中のループ」内の一連の処理です。

コードの詳細の分析に先立ち、このループの目標を確認しましょう。何か気づくことはありますか？

「これは、、、『挿入ソート』に似てますな🤔」

そうですね。似てますよね（打ち合わせどおりの回答ありがとうございます🧡）。以前紹介した「挿入ソート」のコードは、次の通りです。

以前紹介した挿入ソートのコード

細かいところが異なりますが、基本的な処理の流れは、だいたい同じです。そう、この「真ん中のループ」は、挿入ソートの処理を束ねたものなのです！

よし、これで目的は分かりました！

初期値がGapで始まるRange関数の謎

では、コードの詳細に取り組みます。For文の一行目、つまりループの条件式ですね。今回も、Range関数が使われています。

Range関数と言えば、「第１引数以上、第２引数未満」の連番を作ってくれる関数でした。とすると、カウンタ変数は、どう変化しますか？

連番の先頭の値は、Gap、つまり「２」ですね。要素数の半分ですからね。連番の終了値は、「リストの要素数未満」です。要素数は４ですから、「３」になります。

ということは、カウンタ変数「i」は、２→３と変化するのですね。

でも、なんでGapから始まるのかしらん？それは、次のパートで分かります。

未整列エリアの値を、仮の箱に保管せよ

では、次の行です。Tmpという変数にi番目の値を代入していますね。tmpと言えば、仮に値を格納する変数です（好きに付けた名前ですが、慣習的にそうです）。

ループ一回目では、i番目の値は、Gapの値が代入されます。Gap番目の値「２」を上書きされないように逃がしたんでしょうね。イメージで表すと次の通りです。

そうです。挿入ソートで、いずれ挿入する値を、未整列エリア（といっても値が一つですが）から退避させているんですね。ここまでOKだ😄！

退避したあとどうしますか？

はい、「しかるべきところ」に挿入します。その「しかるべきところ」を決める処理は、さらに内側にあるループで行います。この後、「j＝i」という処理がありますが、これは、内側ループのカウンタ変数「j」を初期化しているので、内側ループのときにお話ししましょう。

この行を含めて、内側ループはスキップします。

退避した値を挿入

では、真ん中のループ最後の処理を確認します。下図の赤枠内ですね。これは何をしていますか？

そう、退避したTmpの値を挿入しています。挿入場所は、「ｊ」番目です。「ｊ」という値は、最終的には「挿入される場所の番号」なんだな～ということを頭に入れておくと、内側ループを理解するときに役立つでしょう。

絵にすると次の通りです。

ということで、真ん中のループで行ったことは、
１）挿入する値を取り出す
２）挿入場所を決める（内側ループ）
３）決めた場所に値を挿入する
ということになります。

これで、「真ん中のループ」の全貌が見えました～😉。中ボスを倒しましたね！次回は、ラスボス、内側ループをやっつけましょう！

では、ビーダゼーン！

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