挿入

以前に述べたBubbleでは,ソートを選択することは無条件に位置を変更する方式であったが,ソートを挿入することは必要に応じてのみ位置を変更する.
時間複雑度:O(N^2)で、同じ時間複雑度を持つソートで最も速い

例

まず、挿入ソートが最初の要素1ソートであると仮定する.10は、1의 앞、1과 10 사이2に位置することができるが、10は1よりも大きいので、そのままである.
次に、5を3箇所に配置し、1과 10사이を挿入することができる.
次に、8を4箇所に配置し、5와 10사이を挿入することができる.
.
.
.

インプリメンテーション

github link

def insertion_sort(data):
    for i in range(1, len(data)):
        j = i-1
        while(j>=0 and data[i]<data[j]):
            j -= 1
        data.insert((j+1), data[i])
        del data[i+1]
    return data
    
def insertion_sort2(data):
    for i in range(1, len(data)):
        for j in range(i, 0, -1):
            if (data[j] < data[j-1]):
                data[j], data[j-1] = data[j-1], data[j]
            else:
                break
    return data

if __name__ == "__main__":
    data = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]
    res = insertion_sort2(data)
    print('res: ', res)

まず、最初の要素が整列していると仮定します.
重複データの数:
1(n-1)個のデータを繰り返します.
ソートするj要素をソートの[0~(j-1)]順に入れ、挿入する位置が見つかったら、その位置からスペースを1つ後ろに移動します.
python insert()関数:必要な場所に値を挿入し、挿入位置からセルを1つ後ろに移動します.
a = [1, 2, 3]
a.insert(0, 4)
結果:aは[4,1,2,3]

時間の複雑さ

二重for文が使用されているため時間複雑度はO(N^2)であるが,現在のリストのデータがほぼ整列している場合,O(N)の時間複雑度がある.
References
羅東彬アルゴリズム課