《アルゴリズムを学ぶ》23.クイックソート

# Overview
クイックソート（Quick Sort）は、基準（pivot）となる要素を中心に、小さい値を左、大きい値を右 に分けて再帰的にソートする高速アルゴリズム。
[1.クイックソートの基本](#1-クイックソートの基本)
[2.クイックソートの特徴](#2-クイックソートの特徴)
[3.クイックソートの応用](#3-クイックソートの応用)
[4.典型問題を解いてみる](#4-典型問題を解いてみる)

# 1. クイックソートの基本
### (1) 処理の流れ
1. 基準となる要素（pivot）を選ぶ
2. pivot より小さい要素を左、大きい要素を右に振り分ける
3. 左・右それぞれの部分に再帰的にクイックソートを適用
4. 最終的に結合してソートされた配列ができる

### (2) 再帰を使った簡単な実装（配列をコピーする）
```python
def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[0]
    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]

    return quick_sort(less) + [pivot] + quick_sort(greater)

# 使用例
arr = [10, 3, 5, 2, 8, 7]
print(quick_sort(arr))  # 出力: [2, 3, 5, 7, 8, 10]
```
- 読みやすいが、再帰＆配列のコピーでメモリ効率は悪い

### (3) インプレース実装（メモリ節約版）
```python
def quick_sort_inplace(arr, low, high):
    if low >= high:
        return

    pivot = arr[low]
    left = low + 1
    right = high

    while left <= right:
        while left <= right and arr[left] <= pivot:
            left += 1
        while left <= right and arr[right] >= pivot:
            right -= 1
        if left < right:
            arr[left], arr[right] = arr[right], arr[left]

    arr[low], arr[right] = arr[right], arr[low]

    quick_sort_inplace(arr, low, right - 1)
    quick_sort_inplace(arr, right + 1, high)

# 使用例
arr = [10, 3, 5, 2, 8, 7]
quick_sort_inplace(arr, 0, len(arr) - 1)
print(arr)  # 出力: [2, 3, 5, 7, 8, 10]
```
- 実用ではこちらが好まれる。追加メモリが少なく、速度も速い。

# 2. クイックソートの特徴
### (1) 特徴
- 平均計算量：O(N log N)（非常に高速！）
- 最悪計算量：O(N²)（※ピボット選びが悪いと偏る）
- メモリ使用量：O(log N)
- 非安定ソート（同じ値の順番は保証されない）

### (2) ピボットの選び方
クイックソートの 計算量を安定して $O(N log N)$ に近づけるために、「pivot（基準値）の選び方」が重要。
極端に偏った分割（最小値や最大値を pivot に選ぶなど） だと $O(N^2)$ になる可能性がある。

**よくある pivot の選び方とその特徴**
|方法	|特徴	|計算量の安定性|
|--|--|--|
|先頭（arr[0]）や末尾（arr[-1]）|実装が簡単だが、入力が整列済み・逆順のとき最悪	|× O(N²)になることがある|
|中央（arr[len(arr)//2]）	|データが均等なら良いが、偏りがあると弱い	　      |△ やや改善|
|ランダムに選ぶ	            |入力に関係なく偏りを避けやすい	                |○ 平均 O(N log N)|
|中央値（3つまたは全体の中央値）	|より理想的な分割が可能	                        |○ 最良の精度（ただしコスト高）|
- ランダムに選ぶことで、極端に偏ったケースを防ぎやすい。実用でも高速・安定

# 3. クイックソートの応用
**K 番目に小さい要素を探す（クイックセレクト）**
- クイックソートのアイデアを使って、全体をソートせずに K 番目の値を探す
- 平均 O(N)、最悪 O(N²)

```python
def quick_select(arr, k):
    pivot = arr[0]
    left = [x for x in arr[1:] if x < pivot]
    right = [x for x in arr[1:] if x >= pivot]

    if k <= len(left):
        return quick_select(left, k)
    elif k == len(left) + 1:
        return pivot
    else:
        return quick_select(right, k - len(left) - 1)

# 3番目に小さい要素を求める
arr = [7, 2, 1, 6, 8, 5, 3, 4]
print(quick_select(arr, 3))  # 出力: 3
```

# 4. 典型問題を解いてみる

### 例題1. クイックソート実装
**問題: N 個の整数をクイックソートで昇順に並べよ。**
> [参考： ABC315 B - Quick Sort](https://atcoder.jp/contests/abc315/tasks/abc315_b)
<details><summary> 回答　</summary>

```python
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]
    return quick_sort(less) + [pivot] + quick_sort(greater)

N = int(input())
A = list(map(int, input().split()))
sorted_A = quick_sort(A)
print(*sorted_A)
```
</details>

### 例題2. K 番目に小さい要素を求める（クイックセレクト）
> [参考： ABC318 B - Kth Smallest](https://atcoder.jp/contests/abc318/tasks/abc318_b)
<details><summary> 回答　</summary>

```python
def quick_select(arr, k):
    pivot = arr[0]
    left = [x for x in arr[1:] if x < pivot]
    right = [x for x in arr[1:] if x >= pivot]

    if k <= len(left):
        return quick_select(left, k)
    elif k == len(left) + 1:
        return pivot
    else:
        return quick_select(right, k - len(left) - 1)

N, K = map(int, input().split())
A = list(map(int, input().split()))
print(quick_select(A, K))
```
</details>

### 例題3. 要素を昇順に並べた後の中央値を出力
**問題: 要素をクイックソートで整列し、中央の値を出力**
> [参考： ABC319 C - Median](https://atcoder.jp/contests/abc319/tasks/abc319_c)
<details><summary> 回答　</summary>

```python
A = list(map(int, input().split()))
A = quick_sort(A)
print(A[len(A) // 2])
```
</details>

### 例題4. 昇順降順両方で並べ替える
**問題: クイックソートを使い、昇順と降順両方で表示する**
> [参考： ABC320 B - Sort Both Ways](https://atcoder.jp/contests/abc320/tasks/abc320_b)
<details><summary> 回答　</summary>

```python
arr = list(map(int, input().split()))
sorted_arr = quick_sort(arr)
print("ASC:", *sorted_arr)
print("DESC:", *sorted_arr[::-1])
```
</details>

### 例題5. 数列を並べ替えて辞書順最大にする
**問題: 数列をソートし、辞書順最大になるよう並べる（クイックソート応用）**
> [参考： ABC322 C - Lexicographically Largest](https://atcoder.jp/contests/abc322/tasks/abc322_c)
<details><summary> 回答　</summary>

```python
arr = input().split()
arr = quick_sort(arr)
print("".join(arr[::-1]))
```
</details>