今日学んだこと：挿入ソートに関して

概要

今日は挿入ソートについて学んだ。

ポイント1

• 挿入ソートはリストの整列済みの部分に対して新たな要素を適切な位置に挿入することで整列を行うアルゴリズム

• 整列済みのリストの後ろにいくつかの要素を追加して再び整列させるという場合や、一方の整列済みリストに整列されていない他方のリストを追加しながら整列させたい時に威力を発揮する。

挿入ソートの時間計算量はO(n²)

ポイント2

挿入ソート: 手札に「挿入」 左側のソート済み部分に新要素を挿入

配列での動作

初期配列: [5, 2, 8, 1, 9]
         ↑
      ソート済み部分（最初は1要素）

ステップ1: [5 | 2, 8, 1, 9]  2をソート済み部分に挿入
          → [2, 5 | 8, 1, 9]

ステップ2: [2, 5 | 8, 1, 9]  8をソート済み部分に挿入
          → [2, 5, 8 | 1, 9]

ステップ3: [2, 5, 8 | 1, 9]  1をソート済み部分に挿入
          → [1, 2, 5, 8 | 9]

ステップ4: [1, 2, 5, 8 | 9]  9をソート済み部分に挿入
          → [1, 2, 5, 8, 9]

実装例・コード例

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

    while j >= 0 and[j] > key:
        arr[j + 1] = arr[j]
        j -= 1
    arr[j + 1] = key

参考文献・リンク

https://www.codereading.com/algo_and_ds/algo/insertion_sort.html

---