クイックソートとは？仕組み・計算量・C++実装コードをわかりやすく解説

クイックソートは、リストを2つの部分に分割することで並べ替えを行う高速なソートアルゴリズムです。まず、パーティション（分割）処理によって基準となる「ピボット」要素を選択します。ピボットより小さい値は左側に、大きい値は右側に配置されます。この分割処理が完了した後、それぞれの部分リストに対して同じ手順を再帰的に適用していくことで、全体を整列させます。

クイックソートの計算量

• 時間計算量： 最良ケース・平均ケースで O(n log n)、最悪ケースで O(n²)
• 空間計算量： O(log n)（再帰呼び出しによるスタック領域）

平均的には非常に高速に動作するため、実務でも広く利用されている代表的なソートアルゴリズムの一つです。ただし、すでに整列済みのデータなど特定の入力に対しては最悪計算量 O(n²) になる点には注意が必要です。

入力と出力の例

Input:
The unsorted list: 90 45 22 11 22 50
Output:
Array before Sorting: 90 45 22 11 22 50
Array after Sorting: 11 22 22 45 50 90

アルゴリズム

partition(array, lower, upper)

入力： データ配列 array、下限 lower、上限 upper
出力： 正しい位置に配置されたピボットのインデックス

Begin
    pivot := array[lower]
    start := lower and end := upper
    while start < end do
        while array[start] <= pivot AND start < end do
            start := start + 1
        done

        while array[end] > pivot do
            end := end – 1
        done
        if start < end then
            swap array[start] with array[end]
    done

    array[lower] := array[end]
    array[end] := pivot
    return end
End

quickSort(array, left, right)

入力： データ配列、およびその下限と上限
出力： ソート済みの配列

Begin
    if lower < right then
        q = partition(array, left, right)
        quickSort(array, left, q-1)
        quickSort(array, q+1, right)
End

C++による実装例

以下は、Hoareのパーティション手法を用いたクイックソートのC++実装例です。

#include<iostream>
using namespace std;

void swapping(int &a, int &b) { //aとbの内容を入れ替える
    int temp;
    temp = a;
    a = b;
    b = temp;
}

void display(int *array, int size) {
    for(int i = 0; i<size; i++)
        cout << array[i] << " ";
    cout << endl;
}

int partition(int *array, int lower, int upper) {
    //Hoareの分割手法でピボットの正しい位置を見つける
    int pivot, start, end;
    pivot = array[lower];      //最初の要素をピボットとする
    start = lower; end = upper;

    while(start < end) {
        while(array[start] <= pivot && start<end) {
            start++;       //startポインタを右へ移動
        }

        while(array[end] > pivot) {
            end--;         //endポインタを左へ移動
        }

        if(start < end) {
            swap(array[start], array[end]); //大小の要素を入れ替える
        }
    }

    array[lower] = array[end];
    array[end] = pivot;
    return end;
}

void quickSort(int *array, int left, int right) {
    int q;

    if(left < right) {
        q = partition(array, left, right);
        quickSort(array, left, q-1);     //左側の部分配列をソート
        quickSort(array, q+1, right);    //右側の部分配列をソート
    }
}

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int arr[n]; //指定された要素数の配列を作成
    cout << "Enter elements:" << endl;

    for(int i = 0; i<n; i++) {
        cin >> arr[i];
    }

    cout << "Array before Sorting: ";
    display(arr, n);
    quickSort(arr, 0, n-1); //(n-1)は最後のインデックス
    cout << "Array after Sorting: ";
    display(arr, n);
}

実行結果

Enter the number of elements: 6
Enter elements:
90 45 22 11 22 50
Array before Sorting: 90 45 22 11 22 50
Array after Sorting: 11 22 22 45 50 90

まとめ

クイックソートは、ピボットを基準にデータを分割しながら再帰的に整列を行う効率的なアルゴリズムです。平均時間計算量 O(n log n) と高速である一方、最悪ケースでは O(n²) になる可能性があるため、ピボットの選び方（ランダム選択や中央値など）を工夫することで性能を安定させることができます。