データ構造とアルゴリズム：insertion（挿入ソート）

重要度：高い

左から順に入れ替えていくが、一度入れ替えが起こった後その入れ替えた要素をtmp変数に格納し適切な位置に収まるまで左側の数値と比較して小さい値があったらさらに左へ、また次も小さいければさらに左へというように適切な位置まで左に送るソート。

どんどん左のものと比較して適切な位置に持っていく。

途中経過を確認。

range(1, len_numbers):と１から始めているので、j = i - 1としてjの初期値を0にしてあげる。その後、whileのなかで j -= 1とすることでpirntで出力しているように左側に一つづつ確認していくような処理を実現している。

from typing import List

import random

def insertion_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    for i in range(1, len_numbers):
        tmp = numbers[i]
        j = i - 1
        while j >= 0:
            print(j, end=' ')
            j -= 1
        print()


nums = [random.randint(0,1000) for i in range(10)]
print(insertion_sort(nums))

コード

while j >= 0 and numbers[j] > tmp:となっているので、j >= 0か、numbers[j] > tmpのどちらかが満たされていないとwhile文を抜けることになる。一つづつずらしていき、tmpの数値がnumbers[j]より小さくなったら処理が終了する。

numbers[j+1] = numbers[j]では、左に一つづつずらしている時に、tmpの箱に入っている数値の箇所は空白になるが、それを比較して大きい数値はどんどん右に移動させていくので、numbers[j+1] = numbers[j]とするだけで十分で数値の入れ替えは必要ない。

whileを抜けたら、一番左まで到達したか、tmpの値が適切な位置まで到達した（これ以上小さい値は左側にない）＿ numbers[j+1] = tmpとしてtmpを配列に入れ戻す。 左側に一番小さい数値を入れていくことになるので、[3, 5, 1, 8 , 9, 4]のようなパターンで４を比較した時に1で止まらない？というのは起こり得ない。

4に到達するまでに、1は一番左の要素になっているため

from typing import List
import random

def insertion_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    for i in range(1, len_numbers):
        tmp = numbers[i]
        j = i - 1
        while j >= 0 and numbers[j] > tmp:
            numbers[j+1] = numbers[j]
            j -= 1
        
        numbers[j+1] = tmp
    
    return numbers

nums = [random.randint(0,1000) for i in range(10)]
print(insertion_sort(nums))

[127, 129, 358, 525, 614, 690, 710, 751, 847, 882]