クイックソートとピボット選択
Lomuto方式とHoare方式の分割を使ってクイックソートを構築し、最悪時のO(n²)と、ランダムなピボット選択による緩和方法を学びます。
「クイックソートとピボット選択」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
クイックソート：インプレースの分割統治
クイックソートは、実際に最も広く使われているソートアルゴリズムです。マージソートとは異なり、追加の配列を割り当てずにインプレースでソートします。基本的な考え方は、ピボット要素を1つ選び、ピボットより小さいすべての要素が前に、大きいすべての要素が後ろになるように配列を分割し、その後、それぞれの分割部分を再帰的にソートすることです。分割処理には O(n) 時間かかり、適切なピボットを選べば再帰の深さは O(log n) になります。
def quick_sort(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
pivot_idx = partition(arr, lo, hi)
quick_sort(arr, lo, pivot_idx - 1) # sort left
quick_sort(arr, pivot_idx + 1, hi) # sort right
def partition(arr, lo, hi):
pivot = arr[hi] # Lomuto: choose last element as pivot
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]Lomuto法のパーティション
Lomuto法のパーティションでは、最後の要素をピボットとして使います。遅いポインタ i は「ピボットより小さい」領域の境界を追跡し、速いポインタ j は前方へ走査します。arr[j] <= pivot の場合は i をインクリメントし、arr[i] と arr[j] を交換して、小さい要素の領域を広げます。走査後、arr[hi] と交換して、ピボットを i+1 に配置します。実装は簡単ですが、Hoare法の3倍の交換が発生します。
def lomuto_partition_traced(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
print(f'Pivot: {pivot}, array: {arr[lo:hi+1]}')
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
print(f'After partition: {arr[lo:hi+1]}')
return i + 1
arr = [3, 1, 4, 1, 5, 9, 2, 6]
lomuto_partition_traced(arr, 0, len(arr)-1)Hoare法のパーティション
Hoare法のパーティションでは、両端から開始した2つのポインタを、交差するまで内側へ移動させます。ピボット（通常は先頭要素）を選び、ピボットより小さい要素を左側へ、大きい要素を右側へ移動します。Hoare法は Lomuto法より交換回数が3分の1で、等しい要素がある場合にも適切に動作します。ただし、パーティション後にピボットが最終位置に配置されるわけではないため、再帰呼び出しには少し異なる方法が必要です。
def hoare_partition(arr, lo, hi):
pivot = arr[lo] # first element as pivot
i, j = lo - 1, hi + 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]
def quick_sort_hoare(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
p = hoare_partition(arr, lo, hi)
quick_sort_hoare(arr, lo, p) # note: p not p-1
quick_sort_hoare(arr, p+1, hi)
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort_hoare(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]最悪計算量 O(n²)：すでにソート済みの入力
クイックソートの最悪ケースは、パーティション内でピボットが常に最小要素または最大要素になる場合に発生します。すでにソート済みの配列に Lomuto法の末尾要素ピボットを使うと、パーティションによって常に左側に0要素、右側に n-1 要素が配置されます。その結果、再帰木は深さ n の一本の連鎖になり、比較回数は O(n²) になります。このため、ピボットの選択は重要であり、本番向けの実装ではピボットをランダム化します。
import sys
sys.setrecursionlimit(5000)
def quick_sort_naive(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
comparisons = [0]
def _qs(lo, hi):
if lo >= hi: return
pivot = arr[hi] # last element pivot
i = lo - 1
for j in range(lo, hi):
comparisons[0] += 1
if arr[j] <= pivot:
i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
p = i + 1
_qs(lo, p-1); _qs(p+1, hi)
_qs(lo, hi)
return comparisons[0]
import math
n = 100
sorted_arr = list(range(n))
ops = quick_sort_naive(sorted_arr)
print(f'n={n}, ops={ops}, n^2={n**2}') # ops close to n*(n-1)/2ランダム化ピボット：期待計算量 O(n log n)
ピボットを一様ランダムに選ぶ（パーティションの前にランダムな要素と arr[hi] を交換する）と、悪いピボットを連続して選ぶ確率が指数関数的に低下します。比較回数の期待値は 2n ln(n) ≈ 1.39 n log₂(n) であり、期待時間計算量 O(n log n) が圧倒的に高い確率で得られます。これがランダム化クイックソートが実際に使われる理由です。固定ピボット戦略に対して、悪意ある入力によって作られる病的な最悪ケースを避けられます。
import random
def quick_sort_random(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
# Randomise pivot
rand_i = random.randint(lo, hi)
arr[rand_i], arr[hi] = arr[hi], arr[rand_i]
# Lomuto partition with last element as pivot
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
p = i + 1
quick_sort_random(arr, lo, p - 1)
quick_sort_random(arr, p + 1, hi)
arr = list(range(100, 0, -1)) # worst case for naive
quick_sort_random(arr)
print(arr[:10]) # [1,2,3,4,5,6,7,8,9,10]3要素の中央値を使うピボット
別のピボット戦略として、先頭、中央、末尾の要素の中央値を選ぶ方法があります。これにより、ソート済みまたは逆順にソート済みの入力（最も一般的な敵対的入力）での最悪ケースを避けながら、乱数生成のオーバーヘッドも回避できます。多くの本番向け実装では、大きな配列に対して中央値の中央値（3つの中央値の中央値）である ninther や median-of-three を使い、約10要素未満の小さな部分配列には挿入ソートを使います。
def median_of_three(arr, lo, hi):
mid = (lo + hi) // 2
# Sort lo, mid, hi values in place
if arr[lo] > arr[mid]: arr[lo], arr[mid] = arr[mid], arr[lo]
if arr[lo] > arr[hi]: arr[lo], arr[hi] = arr[hi], arr[lo]
if arr[mid] > arr[hi]: arr[mid], arr[hi] = arr[hi], arr[mid]
# Median is now at arr[mid]; swap to arr[hi-1] as pivot
arr[mid], arr[hi] = arr[hi], arr[mid]
return arr[hi] # pivot value
arr = [3, 9, 1]
print(median_of_three(arr, 0, 2), arr) # 3, [1,3,9] (sorted)Dutch National Flag：3-way partition
標準的なパーティションでは、ピボットより小さい要素を左に、大きい要素を右に配置しますが、ピボットと等しい要素は分散してしまいます。3-way partition（Dutch national flag）は、<pivot、==pivot、>pivot の3つの領域を作ります。これは重複要素が多い配列で非常に重要です。標準的なクイックソートは O(n²) に劣化しますが、3-way クイックソートなら、すべての値が同じ入力に対して O(n) になります。
def three_way_partition(arr, lo, hi):
pivot = arr[lo]
lt = lo # arr[lo..lt-1] < pivot
gt = hi # arr[gt+1..hi] > pivot
i = lo # current
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1; i += 1
elif arr[i] > pivot:
arr[i], arr[gt] = arr[gt], arr[i]
gt -= 1 # don't advance i
else:
i += 1
return lt, gt # pivot occupies arr[lt..gt]
arr = [3, 1, 4, 1, 5, 9, 2, 6, 3, 3]
lt, gt = three_way_partition(arr, 0, len(arr)-1)
print(arr, '| pivot region:', lt, 'to', gt)Quickselect：O(n)でk番目に小さい要素を求める
Quickselectはクイックソートのパーティション処理を使い、配列全体をソートせずに、平均 O(n) 時間で k 番目に小さい要素を見つけます。パーティション後、ピボットは最終位置 p にあります。p == k なら arr[p] を返します。k < p なら左側のパーティションを、k > p なら右側のパーティションを再帰的に処理します。平均すると、各再帰で問題の大きさが半分になります。O(n) + O(n/2) + O(n/4) + ... = O(2n) = O(n) です。
import random
def quickselect(nums, k):
'''Find kth smallest (0-indexed) in O(n) average.'''
def _select(lo, hi):
if lo == hi: return nums[lo]
rand_i = random.randint(lo, hi)
nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
pivot = nums[hi]
i = lo - 1
for j in range(lo, hi):
if nums[j] <= pivot:
i += 1; nums[i], nums[j] = nums[j], nums[i]
p = i + 1
nums[p], nums[hi] = nums[hi], nums[p]
if p == k: return nums[p]
elif k < p: return _select(lo, p - 1)
else: return _select(p + 1, hi)
return _select(0, len(nums) - 1)
print(quickselect([3,2,1,5,6,4], 1)) # 2 (2nd smallest)クイックソートの空間計算量
クイックソートは「インプレース」と呼ばれますが、再帰のために平均 O(log n) のスタック領域を使います（再帰木の各レベルにつき1フレーム）。最悪の場合、スタックの深さは O(n) になります。最悪時でも O(log n) のスタック領域を保証するには、常に小さいパーティションを先に再帰処理し、大きいパーティションには末尾再帰最適化を使います。Python の再帰制限により、非常に深いクイックソートの再帰は危険になり得るため、面接では触れておく価値があります。
def quick_sort_optimised(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
while lo < hi:
p = lomuto_partition_qs(arr, lo, hi)
# Recurse on smaller partition; iterate on larger
if p - lo < hi - p:
quick_sort_optimised(arr, lo, p - 1)
lo = p + 1 # tail-call elimination
else:
quick_sort_optimised(arr, p + 1, hi)
hi = p - 1
def lomuto_partition_qs(arr, lo, hi):
pivot = arr[hi]; i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot: i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1ソートアルゴリズムの比較
ここまでの知識を整理しましょう。
- クイックソート：期待計算量 O(n log n)、最悪計算量 O(n²)、領域 O(log n)、不安定、ランダムなデータでは実際に最速
- マージソート：O(n log n) を保証、領域 O(n)、安定、連結リストと外部ソートに最適
- ヒープソート：O(n log n) を保証、領域 O(1)、不安定、キャッシュミスにより実際には低速
- 挿入ソート：最良計算量 O(n)、小さい n やほぼソート済みのデータに最適
# Python's sorted() uses Timsort:
# - Hybrid: merge sort for large runs, insertion sort for small (< 64 elements)
# - Stable, O(n log n) worst case
# - O(n) best case for sorted/reverse-sorted/nearly-sorted
# - O(n) extra space
import random
arr = random.sample(range(10000), 1000)
sorted_arr = sorted(arr) # Timsort
print(sorted_arr[:5], '...') # first 5 elementsイントロソート：3つすべてを組み合わせる
イントロソート（C++ STL の std::sort で使われています）は、クイックソート、ヒープソート、挿入ソートを組み合わせたものです。まずランダム化クイックソートを開始し、再帰の深さが 2 log n を超えたら（悪いピボットが続いていることを示します）、ヒープソートに切り替えて O(n log n) を保証します。16要素未満の小さな部分配列には挿入ソートを使います。これにより、最悪計算量 O(n log n) を保証しながら、クイックソートの平均時の速度と、挿入ソートの小さな部分配列に対する効率を得られます。
# Introsort hybrid (simplified)
def introsort(arr, depth_limit=None):
if depth_limit is None:
import math
depth_limit = 2 * int(math.log2(len(arr) + 1)) if arr else 0
if len(arr) <= 16:
# insertion sort for small arrays
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1
arr[j+1] = key
return arr
if depth_limit == 0:
arr.sort() # fall back to heapsort equivalent
return arr
# Otherwise quick sort
pivot = arr[-1]
small = [x for x in arr[:-1] if x <= pivot]
large = [x for x in arr[:-1] if x > pivot]
return introsort(small, depth_limit-1) + [pivot] + introsort(large, depth_limit-1)
print(introsort([5,3,8,1,9,2,7]))理解度チェック
このレッスンで学んだ Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認します。
レッスンの振り返り
このレッスンでは、クイックソートはピボットを基準にインプレースで分割し、それぞれの側を再帰的に処理します。これにより、O(log n) のスタック領域で期待時間計算量 O(n log n) を達成し、ランダムなデータでは実際にマージソートより高速です。また、最悪計算量 O(n²) は固定ピボットでソート済みの入力を処理すると発生しますが、ランダム化ピボットや中央値の3要素によるピボット選択で回避できます。さらに、3-way partition は重複要素を効率的に処理し、Quickselect はパーティションの考え方を拡張して、全体をソートせずに平均 O(n) 時間で k 番目に小さい要素を見つけます。次は比較を使わないソートと Python の組み込みソートについて学びます。
よくある質問
「クイックソートとピボット選択」レッスンは無料ですか？
はい。「クイックソートとピボット選択」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「クイックソートとピボット選択」で何を学びますか？
Lomuto方式とHoare方式の分割を使ってクイックソートを構築し、最悪時のO(n²)と、ランダムなピボット選択による緩和方法を学びます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「クイックソートとピボット選択」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- バブルソートと挿入ソート
- マージソート：分割、整列、マージ
- クイックソートとピボット選択
- 比較を使わないソートとPythonのsort()