クイックソート（Quick Sort）はTony Hoareによって1960年に提案され、分治法を用いています。

• 分解：基準要素を選択し、配列を2つに分割します。
• 再帰：左右の部分配列を再帰的にソートします。
• 結合：部分配列が整列された後、全体が自然に整列されます。

基本的な実装例

#include <iostream>
#include <vector>
#include <algorithm>

class QS {
public:
    static void basicSort(std::vector<int>& arr, int start, int end) {
        if (start < end) {
            int pivot = partition(arr, start, end);
            basicSort(arr, start, pivot - 1);
            basicSort(arr, pivot + 1, end);
        }
    }

private:
    static int partition(std::vector<int>& arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; ++j) {
            if (arr[j] <= pivot) {
                ++i;
                std::swap(arr[i], arr[j]);
            }
        }
        std::swap(arr[i + 1], arr[high]);
        return i + 1;
    }
};

void testQS() {
    std::vector<int> data = {5, 3, 8, 4, 2};
    QS::basicSort(data, 0, data.size() - 1);

    for (int num : data) {
        std::cout << num << " ";
    }
}

アルゴリズムの複雑さ解析

最適化テクニック

1. 基準選択の最適化

三数中央値法を使用して、low、mid、highから中間値を選ぶ方法です。

2. 小規模配列の最適化

• 配列サイズが16未満の場合、挿入ソートに切り替えます。
• 挿入ソートは小規模なデータに対して効率的です。

3. 三路クイックソート

• 大量の重複要素を処理するため。
• 配列を<、=、>の三つの部分に分割。
• 重複要素の繰り返し比較を回避します。

4. 末尾再帰の最適化

小さな部分配列を再帰的に処理し、大きな部分配列を反復的に処理する手法です。

while (start < end) {
    int pivot = partition(arr, start, end);
    if (pivot - start < end - pivot) {
        basicSort(arr, start, pivot - 1);
        start = pivot + 1;
    } else {
        basicSort(arr, pivot + 1, end);
        end = pivot - 1;
    }
}

クイックソートとマージソートの比較

使用上のアドバイス

• 一般用途：std::sort()を使用。これはクイックソートの最適化版です。
• 安定性が必要：std::stable_sort()（マージソート）を使用。
• データがほぼ整列されている場合：挿入ソートまたはヒープソートを使用。
• 大量の重複要素がある場合：三路クイックソートを使用。