C++でクイックソートを実装するプログラム|ランダム化で最悪ケースO(n²)を回避

クイックソート(Quick Sort)は「分割統治法(divide-and-conquer)」に基づく高速な整列アルゴリズムです。平均時間計算量は O(n log n) と非常に効率的ですが、ピボットの選び方次第では最悪ケースで O(n²) まで計算量が悪化する可能性があります。
そこで本記事では、乱数を用いてピボットをランダムに選択する「ランダム化クイックソート」をC++で実装し、最悪ケースが発生する確率を大幅に下げる方法を解説します。

アルゴリズム

Partition(int a[], int l, int h)

配列 a の範囲 [l, h] を、ピボットより小さいグループと大きいグループに分割する関数です。末尾の要素をピボットとして扱い、ピボット未満の要素を左側へ寄せた後、ピボットを正しい位置(index)へ移動します。戻り値はピボットの最終的なインデックスです。

Begin
    pivot = h                       // 末尾の要素をピボットとする
    index = l
    start = l、end = h
    while start < end do
        while a[start] <= a[pivot] AND start < end do
            start = start + 1
        done
        while a[end] > a[pivot] do
            end = end − 1
        done
        if start < end then
            a[start] と a[end] を入れ替える
        done
    a[l] = a[end]
    a[end] = a[pivot]
    return end
End

RandomPivotPartition(int a[], int l, int h)

rand() を使って範囲 [l, h] からランダムにピボットを選び、それを末尾(h)の要素と入れ替えてから通常の Partition を呼び出す関数です。入力が既に整列済みなど偏っている場合でも、最悪ケース O(n²) に陥る可能性を効果的に低減できます。

Begin
    n = rand()
    pivot = l + n % (h − l + 1)
    a[h] と a[pivot] を入れ替える
    return Partition(a, l, h)
End

QuickSort(int a[], int l, int h)

整列処理の本体となる再帰関数です。ピボットの位置 pindex を基準に、左部分列 [l, pindex−1] と右部分列 [pindex+1, h] に対してそれぞれ QuickSort を再帰的に呼び出すことで、全体を整列させます。

Begin
    int pindex
    if (l < h)
        pindex = RandomPivotPartition(a, l, h)
        QuickSort(a, l, pindex − 1)
        QuickSort(a, pindex + 1, h)
    return 0
End

C++による実装例

以下は、上記アルゴリズムをそのままC++で実装した完全なサンプルコードです。ユーザーから要素数と各要素の値を入力として受け取り、整列後の結果を出力します。

#include<iostream>
#include<cstdlib>

using namespace std;

void swap(int *a, int *b) {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

int Partition(int a[], int l, int h) {
    int pivot, index, i;
    index = l;
    pivot = h;
    for(i = l; i < h; i++) {
        if(a[i] < a[pivot]) {
            swap(&a[i], &a[index]);
            index++;
        }
    }
    swap(&a[pivot], &a[index]);
    return index;
}
int RandomPivotPartition(int a[], int l, int h) {
    int pvt, n, temp;
    n = rand();
    pvt = l + n%(h-l+1);
    swap(&a[h], &a[pvt]);
    return Partition(a, l, h);
}
int QuickSort(int a[], int l, int h) {
    int pindex;
    if(l < h) {
        pindex = RandomPivotPartition(a, l, h);
        QuickSort(a, l, pindex-1);
        QuickSort(a, pindex+1, h);
    }
    return 0;
}
int main() {
    int n, i;
    cout<<"\nEnter the number of data element to be sorted: ";
    cin>>n;
    int arr[n];
    for(i = 0; i < n; i++) {
        cout<<"Enter element "<<i+1<<": ";
        cin>>arr[i];
    }
    QuickSort(arr, 0, n-1);
    cout<<"\nSorted Data ";
    for (i = 0; i < n; i++)
        cout<<"->"<<arr[i];
    return 0;
}

実行結果

Enter the number of data element to be sorted: 4
Enter element 1: 3
Enter element 2: 4
Enter element 3: 7
Enter element 4: 6
Sorted Data ->3->4->6->7

計算量のまとめ

• 平均時間計算量:O(n log n)
• 最悪時間計算量:O(n²)(ランダムピボット選択により発生確率は極めて低い)
• 空間計算量:O(log n)(再帰呼び出しのスタック領域分)

このように、単純なクイックソートにランダム化を加えるだけで、特定の入力パターンによる性能劣化を防ぎ、実用上ほぼ常に O(n log n) に近い性能を安定して得られるようになります。