Quick Sort
最終更新
クイックソートは「ピボット」を中心に並べ替える分割統治アルゴリズムです。ピボット要素を選び、それより小さいものはすべて前に、大きいものはすべて後ろに来るように配列を分割します。これによりピボットは最終的なソート済みの位置に固定されます。その後、左右の分割に対して再帰します。この可視化では、最後の要素をピボットとする Lomuto 方式を使用します。再生を押して、分割とピボットの配置を確認してください。
クイックソートは、良好なキャッシュ動作とインプレース分割のおかげで、実際には最速の汎用ソートであることが多く、平均は O(n log n) です。最悪計算量は O(n²) で（例えばピボットの選び方が悪いすでにソート済みの配列）、median-of-three やランダム化などの優れたピボット戦略でこれを回避できます。
時間計算量と空間計算量
| ケース | 計算量 | 備考 |
|---|---|---|
| 最良の場合 | O(n log n) | 均衡した分割 |
| 平均的な場合 | O(n log n) | ランダムな順序 |
| 最悪の場合 | O(n²) | 常に不均衡なピボット |
| 空間 | O(log n) | 再帰スタック（インプレース分割） |
| 安定 | いいえ | 分割時のスワップが等しい要素を並べ替える |
ステップごとの手順
| ステップ | 何が起こるか |
|---|---|
| 1 | ピボットを選ぶ（ここでは範囲の最後の要素）。 |
| 2 | 分割：ピボットより小さい要素をすべてその左へ移動する。 |
| 3 | ピボットを境界にスワップする — これで最終的な位置に置かれる。 |
| 4 | 左の分割に対して再帰的にクイックソートを適用する。 |
| 5 | 右の分割に対して再帰的にクイックソートを適用する。 |
具体例による手順
Lomuto 方式（最後の要素をピボット）で [5, 2, 4, 1] をソートする：
| パス | 配列 | 操作 |
|---|---|---|
| 開始 | [5, 2, 4, 1] | 範囲全体を分割する。ピボットは 1（最後の要素）。 |
| 1 | [1, 2, 4, 5] | 1 より小さいものはないので、1 をインデックス 0 にスワップする。ピボット 1 はこれで確定。[2, 4, 5] に対して右へ再帰。 |
| 2 | [1, 2, 4, 5] | ピボット 5 で [2, 4, 5] を分割する。2 も 4 も小さいので 5 は末尾に残り確定。[2, 4] に対して左へ再帰。 |
| 3 | [1, 2, 4, 5] | ピボット 4 で [2, 4] を分割する。2 が小さいので 4 はそのままで確定。2 は要素が1つなのですでにソート済み。 |
| 完了 | [1, 2, 4, 5] | すべてのピボットが所定の位置に固定され、配列はソート済み。 |
クイックソートを使うべきとき
| 使うべき場合 | 避けるべき場合 |
|---|---|
| 定数係数が小さい、高速で汎用的なメモリ内ソートが必要なとき。 | 最悪計算量 O(n log n) の保証が必要なとき（ヒープソートやマージソートを使う）。 |
メモリが限られているとき — 分割はインプレースで行われ、必要なスタックは O(log n) のみ。 | 等しいキーの順序を保つ安定なソートが必要なとき。 |
| データがランダムまたは不明な順序で、ランダムまたは median-of-three のピボットを使うとき。 | 入力がすでにソート済みまたはほぼソート済みで、ピボットが固定されており O(n²) を引き起こすとき。 |
| クイックソートはメモリに逐次アクセスするため、良好なキャッシュ局所性が重要なとき。 | 連結リストをソートするとき。ここではマージソートがクイックソートの依存するランダムアクセスを避けられる。 |
Quick Sortのコード
Python, JavaScript, Java, C++, Cによるクリーンで実行可能なQuick Sortの実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。
PythonでのQuick Sortのコード
Python
1def quick_sort(a, low=0, high=None):2 if high is None:3 high = len(a) - 14 if low < high:5 p = partition(a, low, high)6 quick_sort(a, low, p - 1)7 quick_sort(a, p + 1, high)8 return a9
10
11def partition(a, low, high):12 # Lomuto partition: everything < pivot moves left of it13 pivot = a[high]14 i = low15 for j in range(low, high):16 if a[j] < pivot:17 a[i], a[j] = a[j], a[i]18 i += 119 a[i], a[high] = a[high], a[i]20 return i21
22
23nums = [10, 7, 8, 9, 1, 5]24print("Before:", nums)25quick_sort(nums)26print("After: ", nums)JavaScriptでのQuick Sortのコード
JavaScript
1function quickSort(a, lo = 0, hi = a.length - 1) {2 if (lo >= hi) return a;3 const p = partition(a, lo, hi);4 quickSort(a, lo, p - 1);5 quickSort(a, p + 1, hi);6 return a;7}8
9// Lomuto partition: last element is the pivot10function partition(a, lo, hi) {11 const pivot = a[hi];12 let i = lo;13 for (let j = lo; j < hi; j++) {14 if (a[j] < pivot) {15 [a[i], a[j]] = [a[j], a[i]];16 i++;17 }18 }19 [a[i], a[hi]] = [a[hi], a[i]];20 return i;21}22
23const data = [5, 2, 9, 1, 7, 3];24console.log("Before:", data);25console.log("Sorted:", quickSort([...data]));JavaでのQuick Sortのコード
Java
1import java.util.Arrays;2
3public class Main {4 static void quickSort(int[] arr, int low, int high) {5 if (low >= high) return;6 int p = partition(arr, low, high);7 quickSort(arr, low, p - 1);8 quickSort(arr, p + 1, high);9 }10
11 // Lomuto partition: last element is the pivot12 static int partition(int[] arr, int low, int high) {13 int pivot = arr[high];14 int i = low - 1;15 for (int j = low; j < high; j++) {16 if (arr[j] < pivot) swap(arr, ++i, j);17 }18 swap(arr, i + 1, high);19 return i + 1;20 }21
22 static void swap(int[] arr, int a, int b) {23 int tmp = arr[a];24 arr[a] = arr[b];25 arr[b] = tmp;26 }27
28 public static void main(String[] args) {29 int[] arr = {10, 7, 8, 9, 1, 5};30 System.out.println("Before: " + Arrays.toString(arr));31 quickSort(arr, 0, arr.length - 1);32 System.out.println("After: " + Arrays.toString(arr));33 }34}C++でのQuick Sortのコード
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10// Lomuto partition: place the pivot in its final position11int partition(std::vector<int>& a, int lo, int hi) {12 int pivot = a[hi];13 int i = lo;14 for (int j = lo; j < hi; ++j) {15 if (a[j] < pivot) std::swap(a[i++], a[j]);16 }17 std::swap(a[i], a[hi]);18 return i;19}20
21void quickSort(std::vector<int>& a, int lo, int hi) {22 if (lo >= hi) return;23 int p = partition(a, lo, hi);24 quickSort(a, lo, p - 1);25 quickSort(a, p + 1, hi);26}27
28int main() {29 std::vector<int> data = {10, 7, 8, 9, 1, 5};30 std::cout << "Before: ";31 printVec(data);32 quickSort(data, 0, static_cast<int>(data.size()) - 1);33 std::cout << "After: ";34 printVec(data);35 return 0;36}CでのQuick Sortのコード
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void swap(int* x, int* y) {9 int tmp = *x;10 *x = *y;11 *y = tmp;12}13
14// Lomuto partition: place the pivot in its final position15int partition(int a[], int lo, int hi) {16 int pivot = a[hi];17 int i = lo;18 for (int j = lo; j < hi; j++) {19 if (a[j] < pivot) swap(&a[i++], &a[j]);20 }21 swap(&a[i], &a[hi]);22 return i;23}24
25void quickSort(int a[], int lo, int hi) {26 if (lo >= hi) return;27 int p = partition(a, lo, hi);28 quickSort(a, lo, p - 1);29 quickSort(a, p + 1, hi);30}31
32int main(void) {33 int data[] = {10, 7, 8, 9, 1, 5};34 int n = sizeof(data) / sizeof(data[0]);35 printf("Before: ");36 printArr(data, n);37 quickSort(data, 0, n - 1);38 printf("After: ");39 printArr(data, n);40 return 0;41}Quick Sort よくある質問
クイックソートの時間計算量はどれくらいですか？
クイックソートは平均
O(n log n)、最良の場合も O(n log n) ですが、分割が常に不均衡になる最悪の場合には O(n²) に劣化します。ランダムまたは median-of-three のピボットを使うと、最悪の場合はほとんど起こらなくなります。クイックソートは安定ですか？
いいえ。標準的なインプレース分割は離れた要素をスワップするため、等しいキーの相対順序が変わることがあります。安定な変種も存在しますが、クイックソートのインプレースという利点を手放すことになります。
なぜクイックソートはマージソートより速いことが多いのですか？
クイックソートは優れたキャッシュ局所性を持ち、追加のバッファなしでインプレースに分割するため、定数係数が小さくなります。マージソートは同じ
O(n log n) の上限を達成しますが、O(n) のバッファとより多くのデータ移動のコストを払います。クイックソートとマージソート、どちらを使うべきですか？
メモリ内の配列を高速かつインプレースにソートするならクイックソートを選びましょう。小さな定数係数のおかげでたいてい勝ります。安定なソート、
O(n log n) の最悪計算量保証、あるいは RAM に収まらない連結リストや外部データのソートが必要なときはマージソートを選びましょう。なぜソート済みの配列でクイックソートは O(n²) になるのですか？
最初または最後の要素のような固定ピボットでは、すでにソート済みの入力に対して各分割が要素を1つだけ切り離すため、
log n ではなく n 段の再帰が生じます。ピボットをランダムまたは median-of-three で選ぶとこのパターンが崩れ、O(n log n) の挙動が回復します。Lomuto 方式と Hoare 方式の分割の違いは何ですか？
Lomuto 方式は左から右へ走査する単一のインデックスを使い、コードが単純なため、この可視化ではこれを採用しています。Hoare 方式は内側へ動く2つのポインタを使い、通常スワップが少なく実際には高速ですが、分割ステップの間にピボットを最終的な位置には置きません。
関連リソース
その他の可視化
