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 も必須知識