挿入ソートまとめ

挿入ソートとは？

挿入ソートは以下のような特徴を持つソートアルゴリズムです：

1. 動作原理:

   • 配列を「ソート済み部分」と「未ソート部分」に分ける。
   • 未ソート部分の先頭要素を取り出し、ソート済み部分の適切な位置に挿入する。
   • この操作を繰り返し、全要素をソートする。

2. アルゴリズムの流れ:

   • 配列の2番目の要素から順に処理を行う。
   • 処理中の要素を一時変数に保存。
   • ソート済み部分を右から左に走査し、適切な挿入位置を見つける。
   • 挿入位置より右の要素を1つずつ右にシフトする。
   • 一時変数の値を適切な位置に挿入する。

3. 特徴:

   • 安定なソートアルゴリズム。
   • 小規模なデータセットや、ほぼソート済みのデータに対して効率的。
   • 平均的な時間計算量は O(n^2)。
   • 最良の場合（ほぼソート済み）は O(n)。

4. 実装:

   • 通常、2重ループを使用して実装される。
   • 外側のループは未ソート部分を走査。
   • 内側のループはソート済み部分を走査し、挿入位置を決定。

5. 利点:

   • 実装が比較的簡単。
   • 小さなデータセットに対して効率的。
   • 追加のメモリ空間をほとんど必要としない（in-placeソート）。

インプレースソート(In-place sort)とは

https://zenn.dev/btc/articles/241009_in_place_sort

6. 欠点:
   • 大規模なデータセットに対しては非効率的。
   • 平均的なケースでは、クイックソートやマージソートよりも遅い。

挿入ソートは、その簡潔さと特定の状況下での効率性から、小規模なデータセットやほぼソート済みのデータに対して適しています。また、他のより複雑なソートアルゴリズムの一部としても使用されることがあります。

具体的なコード

挿入ソートのPythonによる具体的な実装例を以下に示します：

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        # keyより大きい要素を右に1つずつ移動
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        # keyを適切な位置に挿入
        arr[j + 1] = key

# 使用例
arr = [64, 34, 25, 12, 22, 11, 90]
print("ソート前:", arr) # ソート前: [64, 34, 25, 12, 22, 11, 90]

insertion_sort(arr)
print("ソート後:", arr) # ソート後: [11, 12, 22, 25, 34, 64, 90]