Pythonでアルゴリズム「シェル・ソート」(7)：挿入する場所を地道に探索

2022年7月19日 12:00

こんにちは！本日もPythonで「シェルソート」の続き、そして最終回でございます。今回は、コードの核となっている「内側ループ」に取り組みます。「外側」「真ん中」と続いて、これが「内側」ループです。これが分かれば、シェルソートは完了ですよ～🙂。

では、早速行ってみよ～。

再び登場！whileループ

例によって、コードの全体像を再掲します。本日取り組むのは、赤枠内のWhileループです。

ぱっと見では、いったい何をしているのかつかみにくいですね。ということで、Whileループの目的を確認します。

結論から言えば、内側ループの目的は、ずばり、「挿入場所を決めること」です。この内側ループの前後で、挿入する値を取り出し、そして、しかるべき場所にその値を挿入する処理を行っています。これを実現するには、挿入する場所を決めないといけないわけですね。

では、上からコードを見ていきますが、最初に確認したいのは、Whileループの一つ手前の行です。下図の赤枠内の1行です。

これは一体何をしているのでしょうか？そう、内側ループのカウンタ変数である「j」の初期値を「i」としています。

となりますと「i」の値がどのように変化するのかを、今一度確認しないといけませんね。

「i」すなわち「ｊの初期値」は、
・外側ループ1回目（間隔２）：２→３
・外側ループ2回目（間隔１）：1→２→３
と変化します。

これをいったん頭の隅に残しておいて、次に行きましょう。

さて、本丸に突入します。Whileループの条件式です。

理解のカギを握るのは、「j-gap」の意味です。「j-gap」は、簡単に言えば、「値が挿入される候補の番号」です。分かりにくい？やはり、絵にしてみましょう！

「ああ、「j-gap」番の箱は、挿入される値と比較される値を保持しているのですね！😄」

ですです。これが分からないとこの先何をしているのか、イミフーになってしまいます😅。

Whileの条件式右側は、「tmpの値が、j-gap番の値より小さいとき」です。これが真なら、j-gapの値は、jの箱に移動します。「しゃあない、場所を譲るか」という感じで。

「偽ならどうすんですかね🤔」

偽なら、whileループ内の処理は実行されませんね。つまりj-gapの値は、場祖を譲らないわけです。「俺の方が小さいからな」ということで。となりますと、挿入する値は、取り出したにもかかわらず、もとの場所に戻ることになります。

さて、これでWhileループは、おしまいかと思いきや、まだ処理がありましたね。

「間隔の値をjから差し引いて、もう一回jに入れなおす」ですね。なんでこんなことをするのでしょうか？

ｊからgapを引いたら？そう、Jの値は「j-gap」になりますね。その上で、whileループにもどってGap分だけ左にずらしたペアの比較を改めて行います。

これを繰り返して、j-gapに値がなくなったら（jがgap未満になったら）、Whileループ停止となります。このとき、J-gapに値がないということは、グループ左端に挿入することが確定します。ここに至る前に、挿入する値が自分より小さい値をj-gapに見つけたら、jの位置に戻ります。

このように内側ループは、ｊの値とj-gapの値を比較して、挿入位置を決めているるのでした。

以上で、内側ループおしまいです。やっと、終わった～。ラスボスも倒せましたね（多分）！私が過去記事で紹介したアルゴリズムのうち、もっともトレースしにくアルゴリズムでした…。

というこで、シェルソート完了です！

では、ビーダゼーン！

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