C++で学ぶクイックソート（QuickSort）の仕組みと実装方法

クイックソートとは

クイックソート（Quicksort）は、比較に基づいて未ソートのリスト（配列）を並べ替えるソートアルゴリズムの一つです。「パーティション交換ソート（partition exchange sort）」とも呼ばれます。

クイックソートは安定ソートではありません。これは、等しい値を持つ要素同士の相対的な順序が保持されないためです。ただし、配列に対してごくわずかな追加メモリだけで動作するため、メモリ効率に優れています。選択ソートと非常に似ていますが、常に最悪のパーティションを選んでしまうわけではない点が異なり、より洗練された形の選択ソートと捉えることもできます。

クイックソートは最も効率的なソートアルゴリズムの一つであり、配列をより小さな配列へ分割していくという考え方に基づいています。その名の通り、一般的なソートアルゴリズムよりも大幅に高速にデータを並べ替えることができます。また、マージソートと同様に、分割統治法（divide and conquer）という問題解決手法に分類されます。

クイックソートのアルゴリズムの流れ

身近な例えを使って説明しましょう。学生の名前が書かれた紙を名前順に並べ替える場面を想像してみてください。おそらく次のような手順で行うことになります。

• 基準値（ピボット）を選ぶ： 分割の基準となる値Lを決めます。この値は「ピボット（Pivot）」と呼ばれます。

• 山を2つに分ける： 紙の束を「A〜L」と「M〜Z」の2つの山に分けます。このとき、2つの山の枚数が同じである必要はありません。

• 同じ操作を繰り返す： 「A〜L」の山と「M〜Z」の山それぞれに対して同じ分割を行い、簡単に並べ替えられる大きさになるまで処理を繰り返します。

• 統合する： 最後に、小さくなった山を順番に重ねていけば、完全にソートされた紙の束が完成します。

このアプローチでは、各分割の段階で再帰（recursion）を用いて、要素数1の配列に到達するまで処理を進めます。分割のたびに山を分け、小さくなった山に対して同じ方法を適用していくのです。こうした特徴から、クイックソートは「パーティション交換ソート」とも呼ばれています。

入力：arr[] = {7,4,2,6,3,1,5}
出力：1 2 3 4 5 6 7

具体例で見る処理の流れ

概念を理解するために、具体的な例を見てみましょう。次の配列を考えます。

50, 23, 9, 18, 61, 32

ステップ1： リストの中からピボットとなる値を決めます（通常は末尾の値）。ここでは、先頭のインデックスを「low」、末尾のインデックスを「high」と呼ぶことにします。

この場合、low = 0、high = 5です。

lowとhighの位置にある値はそれぞれ50と32であり、ピボットの値は32です。

そこでパーティション分割を行い、ピボット（32）が本来あるべき位置に収まるように配列を並べ替えます。ピボットの左側にはそれより小さい要素がすべて、右側にはそれより大きい要素がすべて配置されるようにします。

パーティション処理では、先頭の要素から順にピボットと比較していきます。50は32より大きいため変更せず、次の要素23へ進みます。

再びピボットと比較すると、23は32より小さいため、50と23を入れ替えます。配列は「23, 50, 9, 18, 61, 32」になります。

次の要素9もピボット（32）より小さいため、50と入れ替えると配列は次のようになります。

23, 9, 50, 18, 61, 32

同様に、次の要素18も32より小さいため、配列は以下のように変化します。

23, 9, 18, 50, 61, 32　続く61はピボット（32）より大きいため、変更はありません。

最後に、ピボットと50を入れ替えて、ピボットを正しい位置へ移動させます。

これにより、ピボット（32）が実際の位置に収まり、左側の要素はすべてそれより小さく、右側の要素はすべてそれより大きくなります。

ステップ2： この時点で、配列は次のようになっています。

23, 9, 18, 32, 61, 50（ピボットは32）

ステップ3： 次に、リストを2つの部分に分割します。

• ピボットより前の部分リスト：23, 9, 18
• ピボットより後の部分リスト：61, 50

ステップ4： これらの部分リストに対して、同じ手順を繰り返し適用します。

最終的に、配列は「9, 18, 23, 32, 50, 61」となり、ソートが完了します。

C++によるクイックソートの実装例

以下は、ランダムピボット方式を採用したクイックソートの実装例です。ピボットをランダムに選ぶことで、整列済みデータなどで計算量が悪化する最悪ケースO(n²)の発生を抑えられます。

#include <iostream>
#include <cstdlib>
using namespace std;

// 2つの値を入れ替える関数
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// ピボットを基準に配列を分割する関数
int Partition(int a[], int low, int high) {
    int pivot = high;   // ピボットは末尾の要素
    int index = low;
    for (int 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 = low + rand() % (high - low + 1);
    swap(&a[high], &a[pvt]);
    return Partition(a, low, high);
}

// クイックソート本体（再帰処理）
void QuickSort(int a[], int low, int high) {
    if (low < high) {
        int pindex = RandomPivotPartition(a, low, high);
        QuickSort(a, low, pindex - 1);   // ピボットより前をソート
        QuickSort(a, pindex + 1, high);  // ピボットより後をソート
    }
}

int main() {
    int arr[] = {7, 4, 2, 6, 3, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    QuickSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

コードのポイント

• swap関数： ポインタを受け取り、2つの要素の値を入れ替えます。

• Partition関数： ピボットより小さい要素を左側に集め、最後にピボットを正しい位置へ移動させ、その位置（インデックス）を返します。

• RandomPivotPartition関数： rand()を使って範囲内からランダムにピボットを選び、末尾と交換してから通常のパーティション処理を呼び出します。

• QuickSort関数： パーティションで得られたピボットの位置を境に、左右の部分配列に対して自分自身を再帰的に呼び出します。

計算量の目安

• 平均時間計算量：O(n log n)
• 最悪時間計算量：O(n²)（ピボットの選び方が不適切な場合）
• 空間計算量：O(log n)（再帰のためのスタック領域）

このようにクイックソートは、シンプルな実装ながら高速に動作するため、実務でも広く使われている代表的なソートアルゴリズムです。