Pythonでアルゴリズム「シェル・ソート」(3)：4要素のリストを徹底理解

こんにちは！本日も「シェルソート」です。前回記事では、シェルソートとは何かという一般的な全体像を絵でお示ししました。今回は、次回以降に紹介するコードに対応する形で、数値がどのように動くのかを紹介させてください😄！

これによって、ご紹介するコードの理解が容易になるだけでななありません。加えて、シェルソートでどのように変数や要素が変化しているのか、きちんとトレースできるようになります。

こころの準備はよいですか！？では、いってみましょう😆。

分かりやすさ優先！短いリストを用意

では、ソート対象のリストを用意します。要素４つで構成されるリストです。悲しいことに、小さい数値が末尾側に偏っています。挿入ソートを行うには都合が悪いですね…。これをシェルソートします。

「ちょっと待って。サンプルにしてはリストが短くないか？🤔」

う、はい、短いですね。でも、シェルソートは、他の基本ソートアルゴリズムに比べると、処理が複雑です。ゆえに、皆さま（と私）が理解しやすいように、ソートするデータは短くしてみました。正直にいって、数値をトレースするのが結構大変なのです😅。

リストを２つにグループ化

それでは、リストを2グループに分割します。要素間隔は２、すなわち、一つ置きです。「偶数チーム」と「奇数チーム」に分かれる感じですね。

さて、各グループに属する要素を、それぞれ挿入ソートします。各グループには、値が２つしかないんですけれどもね😅。

間隔＝２の「第1グループ」

よし、では第１グループからやりましょう。挿入ソートは覚えてますか？挿入する値として、未整列の数値の左端の値を取り出して、一度仮保存用の変数に保存する、、、のでしたね。

同じように2番にある「２」をtmpに保存します。0番の「４」は、整列済みという扱いです。

続いて、整列済みの値の右端の値とtmpの大きさを比較するのでした。だとすると、今回はtmpと0番を比較します。0番の方が大きいですね。

整列済み右端の値の方が大きいなら、一つ右に移動していただくのでした。ということで、「４」は2番にご移動いただきます。

もうこれ以上整列済みの値がないので、tmpは、0番に挿入されます。

はい、ソートできましたね。挿入ソートというよりは、交換アルゴリズムの動きに近いですね。

間隔＝２の「第２グループ」

続いて、第２グループも同様にソートします。

3番の値をいったんtmpに保管します。

1番と比較します。1番の方が大きいです。

そうならば、３の値は3番へ移動します。

最後にtmpの値が、1番に収まって挿入完了です。イェイ♪。

以上で間隔２での各ソートが終わりました。途中経過のリストは、次の通りとなりました。小さい値の偏りが少し解消されましたね！

間隔＝１で挿入ソート

今度は、間隔を2分の1にして「１」にします。となれば、お隣さん同士でソートを繰り返す感じになります。次のとおりです。

１番までをソート済みにする

0番が整列済み、1番以降が未整列とイメージしてください。1番を正しい場所に挿入します。

２は１より大きいので、右に移動しtて、空いたところにtmpの１が入りました。

２番までをソート済みにする

今度は、2番にある４を挿入します。おっと1番に入っている2の方が小さかった。tmpに格納された値は、もとに戻ります。

３番まで（最後まで）をソート済みにする

最後に3番目の値です。4の方が大きいので、４は右に移動して3は空いたところに収まります。

これでソートできました～。

以上で、『絵で見るシェルソート』はおしまいです。次回からコードを見ていきましょう。

では、ビーダゼーン！

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