挿入ソート

6.1 挿入ソートの定義

挿入ソート (Insertion Sort) は、1回に1つの要素を配置してソートされた配列（またはリスト）を構築するソートアルゴリズムだよ。未ソートの部分から各要素を取り出して、ソート済みの部分に適切な位置に挿入するんだ。

動作原理:

1. 配列の2番目の要素から始めるよ（最初の要素はソート済みと考える）。
2. 現在の要素を前の要素と比較し、正しい位置が見つかるまで左に移動させる。
3. 配列のすべての要素について、ソート済みの部分に新しい要素を挿入するプロセスを繰り返す。

挿入ソートの時間・空間計算量

時間計算量:

• 最悪の場合: O(n^2) — 要素が逆順に元々並べられているときに起こるよ。
• 平均の場合: O(n^2) — ランダムな配置の要素のときに起こる。
• 最良の場合: O(n) — 要素がすでにソートされているときに起こる。

空間計算量:

O(1) — アルゴリズムは一時値を保持するためのいくつかの変数だけを使用するため、追加のメモリ使用量は一定だよ。

6.2 アルゴリズムの動作解析

アルゴリズムの流れで、こんな感じになるよ:

• 現在の要素がインデックス i にある。
• その左側のすべての要素はすでに小さい順から大きい順にソートされています。
• 私たちは、現在の要素を配列のソートされた部分に挿入しようとしているんだ。

配列のソートされた部分に要素を挿入しようとする様子はこんな感じ:

1. 変数 j はループで i - 1 から 0 までの値を取る。
2. 現在の (i番目) の要素が j番目の要素より小さい場合、j番目の要素を1つ右に移動させるよ。

例: 現在の状況:

• 緑色はすでにソートされた要素。
• ピンク色はまだソートされていない要素。
• 現在の要素はインデックス5で、茶色で示される。

今、私たちは配列のソートされた部分に正しい場所を探し出そうとしている。

ステップ1 — 現在の要素の値を変数 key に記憶する。

ステップ2 — 要素 No4 は key より大きい？（10は5より大きい？）それなら要素 No4 を右に動かす:

ステップ3 — 要素 No3 は key より大きい？（8は5より大きい？）それなら要素 No3 を右に動かす:

ステップ4 — 要素 No2 は key より大きい？（6は5より大きい？）それなら要素 No2 を右に動かす:

ステップ5 — 要素 No1 は key より大きい？（4は5より大きい？）いいえ。それなら要素 key を要素 No2 があった場所に挿入する。

要素 No5 を適切な場所に挿入した後、次の要素 No6 に移動し、配列のソートされた部分で彼に場所を見つけよう：

次に7番目の要素を取る：

そして8番目：

6.3 挿入ソートアルゴリズムの実装

このアルゴリズムをPythonで書くとこんな感じになるよ:

def insertion_sort(arr):
    # 配列の2番目の要素からすべての要素を通過
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1 # key より大きい arr[0..i - 1] の要素を1つずつ前に動かす while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j -= 1
        arr[j + 1] = key # key を正しい位置に挿入する
    return arr  # ソートされた配列を返す
        
# 使用例:
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("ソートされた配列:", sorted_arr)
# 出力: ソートされた配列: [5, 6, 11, 12, 13]

説明:

• 現在の要素を key に保存
• ソートされた部分のすべての要素を右に動かす
• 要素を適切な位置に挿入

アルゴリズムの例

例の配列を取ろう: [12, 11, 13, 5, 6]

1. 最初の通過 (i = 1):

• 11と12を比較し、12を右に移動する。
• 配列: [11, 12, 13, 5, 6]

2. 2回目の通過 (i = 2):

• 13はすでにその場にある。
• 配列: [11, 12, 13, 5, 6]

3. 3回目の通過 (i = 3):

• 5を13, 12, 11と比較し、すべてを右に移動する。
• 配列: [5, 11, 12, 13, 6]

4. 4回目の通過 (i = 4):

• 6を13, 12, 11と比較し、すべてを右に移動する。
• 配列: [5, 6, 11, 12, 13]

すべての要素がソートされたのでアルゴリズムは終了する。