Overview
クイックソート（Quick Sort）は、基準（pivot）となる要素を中心に、小さい値を左、大きい値を右 に分けて再帰的にソートする高速アルゴリズム。
1.クイックソートの基本
2.クイックソートの特徴
3.クイックソートの応用
4.典型問題を解いてみる
1. クイックソートの基本
(1) 処理の流れ
- 基準となる要素（pivot）を選ぶ
- pivot より小さい要素を左、大きい要素を右に振り分ける
- 左・右それぞれの部分に再帰的にクイックソートを適用
- 最終的に結合してソートされた配列ができる
(2) 再帰を使った簡単な実装（配列をコピーする）
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) インプレース実装（メモリ節約版）
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²)
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 個の整数をクイックソートで昇順に並べよ。
回答
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)
例題2. K 番目に小さい要素を求める（クイックセレクト）
回答
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))
例題3. 要素を昇順に並べた後の中央値を出力
問題: 要素をクイックソートで整列し、中央の値を出力
回答
A = list(map(int, input().split()))
A = quick_sort(A)
print(A[len(A) // 2])
例題4. 昇順降順両方で並べ替える
問題: クイックソートを使い、昇順と降順両方で表示する
回答
arr = list(map(int, input().split()))
sorted_arr = quick_sort(arr)
print("ASC:", *sorted_arr)
print("DESC:", *sorted_arr[::-1])
例題5. 数列を並べ替えて辞書順最大にする
問題: 数列をソートし、辞書順最大になるよう並べる（クイックソート応用）
回答
arr = input().split()
arr = quick_sort(arr)
print("".join(arr[::-1]))