見出し画像

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

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

よし早速行ってみよ~。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

さて、リストと間隔の設定が終わると、ループのコードに突入します。さきほど、お話ししたとおり、ループは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)

では、ビーダゼーン!

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




いいなと思ったら応援しよう!