整列挿入

1.説明

ソートの挿入は、ソートされたデータの適切な位置にランダムデータを挿入し、ランダムデータ内のソートされたデータの値と比較してランダムデータをソートするアルゴリズムです.
写真ソース:https://github.com/GimunLee

ランダムデータでは、最初のインデックスの値が整列していると仮定します.

2番目のインデックスの値と1番目のインデックスの値を比較します.
1)2番目のインデックスの値が1番目のインデックスの値より大きい場合、1番目のインデックスの右側に挿入して並べ替えます.
2)2番目のインデックスの値が1番目のインデックスの値より小さい場合、1番目のインデックスの左側に挿入して並べ替えます.

3番目のインデックスの値と2番目のインデックスの値を比較します.
1)3番目のインデックスの値が2番目のインデックスの値より大きい場合は、2番目のインデックスの右側に挿入して並べ替えます.
2)3番目のインデックスの値が2番目のインデックスの値より小さい場合、2番目のインデックスの左側に挿入して並べ替えます.次に、上記の2番目のプロシージャ(2番目のインデックスの値を1番目のインデックスの値と比較)を実行します.

以上の手順を繰り返します.

このアルゴリズムは、選択ソートに比べて実装が困難である可能性がある.しかし,時間的複雑さ(O(n^2)とO(n))は相対的に有効である可能性がある.典型的なランダムデータは、整列する場合があります.

2.コード

for i in range(1, len(array)):
    for j in range(i, 0, -1):
        if array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break

3.参考

https://blog.naver.com/ndb796/221226806398

https://github.com/GimunLee