Overview
挿入ソート（Insertion Sort）は、リストを部分的にソートしながら要素を適切な位置に挿入していくソートアルゴリズム。小規模なデータセット（数十個程度）で高速に動作し、ほぼソート済みの配列にも適している。
1.挿入ソートの基本
2.挿入ソートの応用
3.挿入ソートの特徴
4.典型問題を解いてみる
1. 挿入ソートの基本
数列の左側から順番にソートしていくイメージ。途中の段階では、左側通行から段々とソート済みになり、右側はまだ見ていない数字が残る。
＜アルゴリズムの流れ＞
1.2番目の要素から順に、左側（すでにソート済みの部分）に挿入する位置を探す
2.適切な位置に要素を挿入する
3.最後の要素まで繰り返す
＜基本実装＞
def insertion_sort(arr):
n = len(arr)
for i in range(1, n): # 2番目の要素（index 1）から開始
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key: # 挿入位置を探す
arr[j + 1] = arr[j] # 要素を1つ後ろに移動
j -= 1
arr[j + 1] = key # 挿入
return arr
実行例
arr = [5, 3, 8, 4, 2]
print(insertion_sort(arr)) # 出力: [2, 3, 4, 5, 8]
＜降順の選択ソート＞
def insertion_sort_desc(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] < key: # 降順に変更
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
2. 挿入ソートの応用
＜二分探索を用いた挿入ソート（Binary Insertion Sort）＞
通常の挿入ソートでは適切な挿入位置を線形探索するが、二分探索を使うと高速化できる。
import bisect
def binary_insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
pos = bisect.bisect_left(arr[:i], key) # 挿入位置を二分探索で見つける
arr = arr[:pos] + [key] + arr[pos:i] + arr[i+1:]
return arr
3. 挿入ソートの特徴
時間計算量 : 最悪・平均: $O(N^2)$ 最良：$O(N)$（ほぼソート済みの場合）
空間計算量 : $O(1)$ (追加メモリ不要）
安定ソート : Yes（同じ値の順番が保持される）
適用場面 : 小規模データセット、ほぼソート済みのデータ
4. 典型問題を解いてみる
例題1. 挿入ソートの基本
問題: N 個の整数が与えられる。それらを挿入ソートで昇順に並べ替えよ。
回答
N = int(input())
A = list(map(int, input().split()))
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
print(*insertion_sort(A))
例題2. 挿入ソートの比較回数
問題: N 個の整数が与えられる。それらを挿入ソートで並べ替える際の「比較回数」を出力せよ。
回答
N = int(input())
A = list(map(int, input().split()))
def insertion_sort_count(arr):
n = len(arr)
count = 0
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
count += 1 # 比較回数をカウント
arr[j + 1] = key
return count
print(insertion_sort_count(A))
例題3. 降順の挿入ソート
問題: N 個の整数が与えられる。それらを挿入ソートで降順（大きい順）に並べ替えよ。
回答
N = int(input())
A = list(map(int, input().split()))
def insertion_sort_desc(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] < key: # 降順に変更
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
print(*insertion_sort_desc(A))
例題4. K 回だけ挿入ソートを適用
問題: N 個の整数が与えられ、挿入ソートを K 回だけ適用した時点の配列を出力せよ。
回答
N, K = map(int, input().split())
A = list(map(int, input().split()))
def partial_insertion_sort(arr, k):
n = len(arr)
for i in range(1, min(k + 1, n)): # 最大K回までループ
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
print(*partial_insertion_sort(A, K))
例題5. 挿入ソート後の k 番目の要素を出力
問題: N 個の整数が与えられ、それを挿入ソートした後、K 番目の要素を出力せよ。
回答
N, K = map(int, input().split())
A = list(map(int, input().split()))
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
sorted_A = insertion_sort(A)
print(sorted_A[K-1])