【C++】ピボットをランダムに選択するランダム化クイックソートの実装方法

クイックソートは、リストを2つの部分に分割することでソートを行う代表的なアルゴリズムです。まずパーティション(分割)処理によってピボット要素が選択され、ピボットより小さい値は左側へ、大きい値は右側へ配置されます。その後、分割された各部分リストに対して同じ手順を再帰的に適用していきます。

本記事で取り上げるのは、ピボット要素をランダムに選択する「ランダム化クイックソート」です。固定ルールでピボットを選ぶ場合、整列済みやほぼ整列済みのデータを入力すると最悪計算量O(n²)に陥る可能性がありますが、ピボットをランダムに選ぶことでこのリスクを大幅に軽減できます。ピボット選択後は通常どおりパーティション分割を行い、残りの範囲を再帰的にソートします。

クイックソートの計算量

• 時間計算量 − 最良ケース・平均ケースはO(n log n)、最悪ケースはO(n²)

• 空間計算量 − O(log n)

入力 − ソート前のリスト: 90 45 22 11 22 50
出力 − ソート後の配列: 11 22 22 45 50 90

アルゴリズム

partition(array, lower, upper)

入力 − データセットの配列、下限境界、上限境界

出力 − 正しい位置に配置されたピボット

Begin
    index := lower
    pivot := higher
    for i in range lower to higher, do
        if array[i] < array[pivot], then
            exchange the values of array[i] and array[index]
            index := index + 1
    done
    exchange the values of array[pivot] and array[index]
End

random_pivot_partition(array, lower, upper)

入力 − データセットの配列、下限境界、上限境界

出力 − ランダムに選ばれたピボットの最終インデックス

Begin
    n := a random number
    pvt := lower + n mod (upper – lower + 1)
    exchange the values of array[pvt] and array[upper]
    index := Partition(array, lower, upper)
    return index
End

quickSort(array, left, right)

入力 − データの配列、およびその下限と上限

出力 − ソート済みの配列

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

サンプルコード(C++)

#include<iostream>
#include<cstdlib>
#include<ctime>
#define MAX 100
using namespace std;

// 配列の要素をランダムな位置にシャッフルする関数
void random_shuffle(int arr[]) {
    srand(time(NULL));
    for (int i = MAX - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

// 末尾の値をピボットとして配列をパーティション分割する
int Partition(int a[], int low, int high) {
    int pivot, index, i;
    index = low;
    pivot = high;
    for (i = low; i < high; i++) {
        // ピボットの最終位置を求める
        if (a[i] < a[pivot]) {
            swap(a[i], a[index]);
            index++;
        }
    }
    swap(a[pivot], a[index]);
    return index;
}

// ピボットをランダムに選択する
int RandomPivotPartition(int a[], int low, int high) {
    int pvt, n;
    n = rand();
    pvt = low + n % (high - low + 1); // 部分配列からピボットをランダムに決定
    swap(a[high], a[pvt]);
    return Partition(a, low, high);
}

// リストを再帰的にソートする
void quick_sort(int arr[], int p, int q) {
    if (p < q) {
        int pindex = RandomPivotPartition(arr, p, q); // ランダムにピボットを選択
        // QuickSortを再帰的に適用
        quick_sort(arr, p, pindex - 1);
        quick_sort(arr, pindex + 1, q);
    }
}

int main() {
    int arr[MAX];
    for (int i = 0; i < MAX; i++)
        arr[i] = i + 1;
    random_shuffle(arr); // 配列をランダムに並べ替え
    quick_sort(arr, 0, MAX - 1); // 配列の要素をソート
    for (int i = 0; i < MAX; i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

実行結果

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

このサンプルコードでは、1から100までの整数を持つ配列を作成した後、random_shuffle関数で要素をランダムに入れ替え、その状態からquick_sort関数で昇順にソートしています。RandomPivotPartition関数がrand()を用いて各再帰呼び出しのたびにピボットを無作為に選ぶことで、入力データの並び順に偏りがあっても安定した性能を発揮できるのがポイントです。