【Python】挿入ソート

概要

挿入ソートは、効率的なソートアルゴリズムの一つで、小規模なデータセットや既にほぼ整列されているリストに対しては非常に効果的です。未ソートの部分から1つの要素を取り出し、適切な位置に挿入していくことで、リスト全体をソートします。
計算量は O(n^2) で、バブルソートや選択ソートと同等のパフォーマンスですが、ほぼ整列済みのリストに対しては高速です。

この記事では、Pythonでの挿入ソート実装方法について説明します。

コード

以下がPythonでの挿入ソートの実装例です。

def insertion_sort(arr):
    n = len(arr)
    # 1つ目の要素はすでにソート済みとして処理開始
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        # keyがソート済み部分の適切な位置に入るまで移動
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# サンプルの使用例
if __name__ == "__main__":
    sample_data = [12, 11, 13, 5, 6]
    print("ソート前:", sample_data)
    sorted_data = insertion_sort(sample_data)
    print("ソート後:", sorted_data)

実行結果

上記のコードを実行すると、次のような結果が得られます。

ソート前: [12, 11, 13, 5, 6]
ソート後: [5, 6, 11, 12, 13]

詳細

insertion_sort関数は、リストarrを入力として受け取り、挿入ソートの手法を使ってソートされたリストを返します。
外側のforループでは、リストの未ソート部分から1つの要素（key）を取り出し、それをソート済み部分の適切な位置に挿入します。
内側のwhileループでは、ソート済み部分の要素を順次比較し、keyより大きい要素を右にシフトさせることで、keyの挿入位置を確保します。

参考