Overview
クイックソートは平均 O(N log N)、最悪 O(N²) で動作し、実用では最速クラスの比較ソートとして広く使われている。
1.クイックソートの基本
2.クイックソートの特徴
3.インプレースクイックソート
4.クイックセレクト（Quick Select）
5.典型問題を解いてみる
6.まとめ
1. クイックソートの基本
(1) クイックソートとは
クイックソート（Quick Sort）は、基準（pivot）となる要素を中心に
小さい値を左、大きい値を右 に分割し、再帰的に整列する高速なソートアルゴリズム。
- 平均計算量：O(N log N)
- 最悪計算量：O(N²)（pivot が極端に偏ったとき）
- メモリ：O(log N)（再帰スタック）
- 非安定ソート
分割統治法（Divide and Conquer）の代表的なアルゴリズム。
(2) 処理の流れ
- pivot（基準値）を選ぶ
- pivot より小さい値を左、大きい値を右に分割
- 左右の部分配列に再帰的にクイックソートを適用
- 全体が整列される
(3) 配列コピー版の簡単実装（説明向け）
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]
- 読みやすいが、配列のコピーが多くメモリ効率は低い
2. クイックソートの特徴
(1) 計算量
| ケース | 計算量 | 理由 |
|---|---|---|
| 平均 | O(N log N) | 分割が均等に近い |
| 最悪 | O(N²) | pivot が偏り、片方に寄る |
| 空間 | O(log N) | 再帰の深さ（平均） |
(2) ピボットの選び方
| 方法 | メリット | デメリット |
|---|---|---|
| 先頭／末尾 | 実装が簡単 | 整列済み入力で最悪 O(N²) |
| 中央要素 | 偏りをやや回避 | 均等とは限らない |
| ランダム | 偏りをほぼ回避できる | 乱数呼び出しのコスト |
| 中央値（3点 or 全体） | 最も安定 | 計算コストが高い |
(3) Partition法は2種類ある
Lomuto partition（シンプル）
def lomuto_partition(arr, low, high):
pivot = arr[high]
i = low
for j in range(low, high):
if arr[j] <= pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[high] = arr[high], arr[i]
return i
Hoare partition（交換回数が少なく実務向け）
Hoare partition は swap が少なく、また部分配列の分割境界も安定しやすいため、
実務レベルでは Lomuto より平均して高速に動作する。
def hoare_partition(arr, low, high):
pivot = arr[(low + high) // 2]
i = low - 1
j = high + 1
while True:
i += 1
while arr[i] < pivot:
i += 1
j -= 1
while arr[j] > pivot:
j -= 1
if i >= j:
return j
arr[i], arr[j] = arr[j], arr[i]
3. インプレースクイックソート
以下は Hoare partition を使った実用的な in-place 実装。
Python では再帰の深さがデフォルト 1000 のため、pivot が偏ると RecursionError になる可能性がある。
実務では iterative 実装や introsort がよく用いられる。
def quick_sort_inplace(arr, low, high):
if low >= high:
return
p = hoare_partition(arr, low, high)
quick_sort_inplace(arr, low, p)
quick_sort_inplace(arr, p + 1, high)
(1) Stack Overflow を避けるテクニック
- pivot をランダムにする（偏りを避ける）
- 小さい方の区間を先に再帰し、大きい区間は while にする（tail recursion optimization）
- introsort（QuickSort + HeapSort のハイブリッド）を使う
→C++ STL のsort()が採用
4. クイックセレクト（Quick Select）
配列全体をソートせず K 番目に小さい要素だけ を求められる。
- 平均 O(N)
- 最悪 O(N²)
- アイデアは QuickSort と同じ
配列: [7, 2, 1, 6, 8, 5, 3, 4]
3 番目に小さい値を求める
①pivot = 7 で分割
pivot = 7
左（小さい値） : [2, 1, 6, 5, 3, 4]
右（大きい値） : [8]
[7]
┌─────────┴──────────┐
[2, 1, 6, 5, 3, 4] [8]
左側は 6 個あり、
3番目は左側にある と分かるので右側も pivot も無視。
次の探索範囲：
[2,1,6,5,3,4]
②pivot = 2 で分割
pivot = 2
左: [1]
右: [6, 5, 3, 4]
左1個 → pivot は「2番目」
よって、
3番目 → 右側の 1番目
③pivot = 6
pivot = 6
左: [5, 3, 4]
右: []
次は：
[5, 3, 4] の 1番目（= 最小）
④pivot = 5
pivot = 5
左: [3, 4]
右: []
次は：
[3, 4] の 1 番目
⑤pivot = 3 → 決定！
pivot = 3
左: []
右: [4]
左が 0 個なので、
pivot が 1 番目 → 求める値 = 3
※ QuickSelect はソートではなく「K番目の要素」を見つけるだけなので、
不要な側の探索を完全に切り捨てられるのが QuickSort との最大の違い。
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)
5. 典型問題を解いてみる
※ AtCoder 形式に合わせたオリジナル問題です。
例題1. クイックソート実装
問題: N 個の整数をクイックソートで昇順に並べよ。
回答
N = int(input())
A = list(map(int, input().split()))
print(*quick_sort(A))
例題2. pivot による一回の partition 結果を出力
問題: pivot=A[0] を使い、1 回 partition した結果（左 + pivot + 右）を表示せよ。
回答
A = list(map(int, input().split()))
pivot = A[0]
left = [x for x in A[1:] if x <= pivot]
right = [x for x in A[1:] if x > pivot]
print(*left, pivot, *right)
例題3. K 番目に小さい要素（QuickSelect）
回答
N, K = map(int, input().split())
A = list(map(int, input().split()))
print(quick_select(A, K))
例題4. Hoare partition の返す位置を求める
※ Hoare partition の動作理解問題
回答
A = list(map(int, input().split()))
idx = hoare_partition(A, 0, len(A) - 1)
print(idx)
6. まとめ
- QuickSort は 平均 O(N log N) の高速ソート
- pivot の選び方で性能が大きく変わる
- partition 法は Lomuto / Hoare の2種類を理解する
- 実務では in-place + Hoare が多い
- K番目の要素を求める QuickSelect も必須知識