bubble sort、insertion sort、selection sort を説明してください。

Question

Accepted Answer

これらは 3 つの単純な **O(n²)** comparison sort です。large input では遅いですが、sorting の mechanics を理解するのに役立ちます。

## それぞれの仕組み

- **Bubble sort:** adjacent out-of-order pairs を繰り返し swap し、大きい値を各 pass で end へ "bubble" させる。
- **Selection sort:** unsorted part の minimum を見つけ、正しい位置へ swap する。
- **Insertion sort:** sorted prefix を伸ばし、新しい element を正しい位置へ insert する。

## 例（insertion sort）

```python
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]                  # 配置する element
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]       # 大きい element を右へ shift
            j -= 1
        arr[j + 1] = key              # gap に key を置く
    return arr

insertion_sort([5, 2, 4, 1])          # -> [1, 2, 4, 5]
```

## Comparison

| Sort | Best | Worst | Stable | In-place |
|------|------|-------|--------|----------|
| Bubble | O(n) | O(n²) | Yes | Yes |
| Selection | O(n²) | O(n²) | No | Yes |
| Insertion | O(n) | O(n²) | Yes | Yes |

## いつ使うか / pitfalls

Insertion sort は **small or nearly-sorted** array では実際に速く、hybrid sort の内部でも使われます。large unsorted data では 3 つとも避け、O(n log n) sort を使います。

## なぜ重要なのか

これらの sort は invariant、swap、stability の直感を作ります。特に insertion sort は Timsort など production sort の tiny subarray でも使われます。なぜ O(n²) なのかを理解すると、O(n log n) sort の価値が分かります。

Sort	Best	Worst	Stable	In-place
Bubble	O(n)	O(n²)	Yes	Yes
Selection	O(n²)	O(n²)	No	Yes
Insertion	O(n)	O(n²)	Yes	Yes