アルゴリズム？プログラミング。 - 挿入ソート

挿入ソート、insertion sortです。

１．０番目と１番目の要素を比較し、順序が逆であれば入れ換える。
２．2番目の要素について、０番目・１番目の順に比較し、順序が整うように適切な位置へ挿入する
３．3番目以降の要素も同様にして、整列済みデータとの比較と挿入を繰り返す。

https://tetoblog.org/2021/05/insertionsort-python/

左端(0番目)をまず整列済として処理は1番目の数字から処理していきます。

選択ソートでは左端の数字を最小の数字にして整列済にします。一度決めたら変更しません。リスト全体から最小の数字を探してから左端に追加します。
最小、最小、・・・
と繋がっていきます。

挿入ソートは左端の数字は整列済として処理しますが、比較する数字はリスト全体ではなく、整列済とした数字の中でさらに比較して並び替えます。

整列済、整列済・・・

リストの対象の数字を整列済の中に入れるときに整列済の中で大小を比較して対象の数字が整列済の中で順番に並ぶような場所に挿入します。

挿入ソート（基本挿入法）とは | 分かりやすく図解で解説

挿入の処理の内容ですが、
まずリストです。これを並び替えします。

nums = [8,4,1,5]

for in文を使って連続で処理するようにします。左はしnums[0]は整列済と考えます。なので処理を開始する数字はnums[1]からなので以下となります。

for i in range(1, len(nums)):

対象の数字を変数に記憶しておきます。

tmp = nums[i]　・・・　挿入する"i"番目の数字を記憶(退避)しておきます。

挿入する前の数字を定義します。比較対象になります。

j = i - 1　・・・　取り出した"i" より左側、整列済の数字を"j"に代入します

ここで"i"と"j"ですが、リストの並びからいけば、"i"の方が右側です。

[ j ,  i ]

という並びになります。あと、tempはnums[i]で指定される数字です。"i"は順番に変わっていき、それぞれ挿入していきます。

while j >= 0 and nums[j] > tmp:

条件として、"j"は"0"以上で、挿入する数字"tmp"より"num[i]"が大きい時に以下処理します。

 nums[j + 1] = nums[j]
           j -= 1

nums[j + 1] = nums[j]　　・・・　条件が満たされる場合、同じ数字に。

同じ数字にすることで挿入する場所を作っています。

"while"なので、条件をチェックしてもし条件に合わなけらば処理を抜けて

nums[j + 1] = tmp

その時の"j"のインデックスのすぐ後ろに挿入します。

流れをprint()関数で出力してもます。

nums = [8,4,1,5]

for i in range(1, len(nums)):

        tmp = nums[i]

        print(f"{i}回目")

        print(tmp)

        j = i - 1

        while j >= 0 and nums[j] > tmp:
            nums[j + 1] = nums[j]
            j -= 1

            print(nums)

        print(tmp)

        nums[j + 1] = tmp

        print(nums)

#最後
print(nums)

出力は(最初のリストは[8,4,1,5])

1回目
4　　・・・　挿入対象の数字
[8, 8, 1, 5]
4
[4, 8, 1, 5]

2回目
1　　・・・　挿入対象の数字
[4, 8, 8, 5]
[4, 4, 8, 5]
1
[1, 4, 8, 5]

3回目
5　　・・・　挿入対象の数字
[1, 4, 8, 8]
5
[1, 4, 5, 8]

#最後
[1, 4, 5, 8]　・・・　全て整列済。

一つ前の数字を同じものにして最後に数字をtmpの数字に入れ替える操作の連続で並び替えます。

全体です。

nums = [8,4,1,5]

for i in range(1, len(nums)):
        tmp = nums[i]
        j = i - 1

        while j >= 0 and nums[j] > tmp:
            nums[j + 1] = nums[j]
            j -= 1

        nums[j + 1] = tmp

print(nums)