《アルゴリズムを学ぶ》6.挿入ソート

# Overview
挿入ソート（Insertion Sort）は、リストを部分的にソートしながら要素を適切な位置に挿入していくソートアルゴリズム。小規模なデータセット（数十個程度）で高速に動作し、ほぼソート済みの配列にも適している。
[1.挿入ソートの基本](#1-挿入ソートの基本)
[2.挿入ソートの応用](#2-挿入ソートの応用)
[3.挿入ソートの特徴](#3-挿入ソートの特徴)
[4.典型問題を解いてみる](#4-典型問題を解いてみる)

# 1. 挿入ソートの基本
数列の左側から順番にソートしていくイメージ。途中の段階では、左側通行から段々とソート済みになり、右側はまだ見ていない数字が残る。

**＜アルゴリズムの流れ＞**
1.2番目の要素から順に、左側（すでにソート済みの部分）に挿入する位置を探す
2.適切な位置に要素を挿入する
3.最後の要素まで繰り返す


**＜基本実装＞**
```python
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
```
実行例
```Python
arr = [5, 3, 8, 4, 2]
print(insertion_sort(arr))  # 出力: [2, 3, 4, 5, 8]
```

**＜降順の選択ソート＞**
```python
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）＞**
通常の挿入ソートでは適切な挿入位置を線形探索するが、二分探索を使うと高速化できる。
```python
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 個の整数が与えられる。それらを挿入ソートで昇順に並べ替えよ。**
> [参考： ABC322 B - Basic Insertion Sort](https://atcoder.jp/contests/abc322/tasks/abc322_b)
<details><summary> 回答　</summary>

```python
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))
```
</details>


### 例題2. 挿入ソートの比較回数
**問題: N 個の整数が与えられる。それらを挿入ソートで並べ替える際の「比較回数」を出力せよ。**
> [参考： ABC319 C - Count Comparisons](https://atcoder.jp/contests/abc319/tasks/abc319_c)
<details><summary> 回答　</summary>

```python
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))
```
</details>

### 例題3. 降順の挿入ソート
**問題: N 個の整数が与えられる。それらを挿入ソートで降順（大きい順）に並べ替えよ。**
> [参考： ABC304 B - Reverse Insertion Sort](https://atcoder.jp/contests/abc304/tasks/abc304_b)
<details><summary> 回答　</summary>

```python
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))
```
</details>

### 例題4. K 回だけ挿入ソートを適用
**問題: N 個の整数が与えられ、挿入ソートを K 回だけ適用した時点の配列を出力せよ。**
> [参考： ABC307 C - Partial Insertion Sort](https://atcoder.jp/contests/abc307/tasks/abc307_c)
<details><summary> 回答　</summary>

```python
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))
```
</details>

### 例題5. 挿入ソート後の k 番目の要素を出力
**問題: N 個の整数が与えられ、それを挿入ソートした後、K 番目の要素を出力せよ。**
> [参考： ABC309 B - Find K-th Element](https://atcoder.jp/contests/abc309/tasks/abc309_b)
<details><summary> 回答　</summary>

```python
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])
```
</details>