【解説】 挿入ソート
アルゴリズムの仕組み
考え方は非常にシンプルで、**「まだ並び替えていない部分から一番小さいものを探し、左に詰めていく」**という流れです。
-
リスト全体の中から、最小値を探します。
-
見つかった最小値と、未整列部分の先頭の要素を入れ替えます。
-
「最小値が確定した部分」を一つ右へ進め、残りの部分で再び最小値を探します。
-
これを未整列の要素がなくなるまで繰り返します。
特徴と性能
バブルソートと同様に、仕組みは簡単ですが、データの量が増えると時間がかかるタイプです。
-
時間計算量: O(n^2)
-
どんなデータ状態（既に整列されていても、逆順でも）であっても、必ず最後まで比較を行うため、常にこの時間がかかります。
-
-
空間計算量: O(1)
-
安定性: 不安定なソート
-
離れた場所にある要素同士を入れ替えるため、同じ値の要素の前後関係が崩れる可能性があります。
-
# 挿入ソートのコード
def insertion_sort(arr):
n = len(arr)
# 2番目の要素（インデックス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
# 空いた場所にkeyを挿入
arr[j + 1] = key
return arr
# 使用例
data = [12, 11, 13, 5, 6]
sorted_data = insertion_sort(data)
print(f"ソート後: {sorted_data}")