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