Pythonでアルゴリズム「シェル・ソート」(４)：ざっくり分かる！コードの全体像と３つのループたち

こんにちは！今回から、いよいよ「シェルソート」のコードを見ていきましょう。どのような過程を経てソートされるかは、前回記事で確認したところですので、きっとスムーズにコードの内容もご理解いただけます😆。

よし早速行ってみよ～。

簡単そうに見えて実は…！？コードの全体像

先にコードの全体像を見てみましょう。次の画像の通りです。画像最下部を見ると、処理の結果、きちんとソートされていることが分かります。

「コードもそんなに長くないし、思ったより簡単かな～🙂」

確かに、そんなに長くはないですね。でも、よく見てください。ループは何個ありますか？

「入れ子状に３つですね…😑。」

はい。いつもよりも多いですね。こんなところからも、これまで紹介したアルゴリズムに比べて理解するのに、もっとエネルギーが必要そうなことが感じられます。が！ここを乗り越えたら一歩先のレベルに上れる気がしませんか？

丁寧に解説しますから、なんとか一緒に乗り越えましょう😄！

要素の「間隔」を初期設定しよう！

まずは、コードの冒頭部分から見てみましょう。次のところです。

ここは、特に難しいことはありません。ソート対象のデータをリスト名dataとして準備しました。

そして、2行目はのGapって何でしょうか？実は、Gapという言葉からも推測できるとおり、グループ化する際の「要素の間隔」を格納させます。

右辺は、リストの要素数をlen関数で求めて、それを2で割った時の商です。となりますと、要素数４÷２ですから、変数Gapは「２」で初期化されます。

まずは、「要素の間隔は「２」で設定されたんだな」ということを頭の片隅に残しておきましょう。

ざっくり分かる！3つのループの役割

さて、リストと間隔の設定が終わると、ループのコードに突入します。さきほど、お話ししたとおり、ループは３つあって、しかも入れ子になっています。分かりやすいようにループのブロックを色分けして囲ってみました。

コードの詳細にいきなり入るのではなく、これらのループが何をしているのか、ざっくり把握しておきましょう。その方がきっとコードが理解しやすいはず。

まず、一番外側の赤枠です。ここでは、ループの都度、要素の間隔が半分にしています。

続いて、真ん中の水色の枠です。ここでは、挿入ソートを行っています。未整列エリアから値を順々に一つ取り出していきます。そして、その取り出した値を挿入します。

最後に、一番内側の緑色の枠です。このループの狙いは、上記で取り出した値が、整列済みエリアのどこに入るのか見つけることです。取り出した値の方が、整列済みエリアの値より小さいなら、その整列済みエリアの値を右に移動させて、スペースを作ります。

はい、3つのループの役割が何となくわかっていただけましたか？いや、なんとなくでいいです。コードの詳細は、次回以降に回しましょう！

以上、シェルソートのコードの概要でした。

おっと、本日のコードを貼り付けておきます。

data = [4,3,2,1]
gap = len(data) // 2

while gap > 0:
    for i in range(gap, len(data)):
        tmp = data[i]
        j = i
        while j >= gap and data[j - gap] > tmp:
            data[j] = data[j - gap]
            j -= gap
        data[j] = tmp
    gap = gap // 2

print(data)

では、ビーダゼーン！

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