C++ クイックソート徹底解説！実装方法と最適化

クイックソートは一般的に使用されるソートアルゴリズムであり、基本的な考え方は、配列を再帰的に二つのサブ配列に分割し、それぞれをソートすることです。具体的な手順は次の通りです：

1. 配列の中から任意の要素を選択して、基準値とします。
2. 配列を２つに分けて、左側の要素が基準値よりも小さく、右側の要素が基準値よりも大きくなるようにします。
3. 左右のサブ配列を再帰的にソートする。
4. 左右の子配列を結合して、最終的なソートされた配列を得る。

C++でクイックソートを実装するコードの例は以下のとおりです：

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int i = low, j = high, pivot = arr[low];
        while (i < j) {
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            if (i < j) {
                arr[i++] = arr[j];
            }
            while (i < j && arr[i] < pivot) {
                i++;
            }
            if (i < j) {
                arr[j--] = arr[i];
            }
        }
        arr[i] = pivot;
        quickSort(arr, low, i - 1);
        quickSort(arr, i + 1, high);
    }
}

// 使用方法
vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
quickSort(arr, 0, arr.size() - 1);

上記のコードでは、最初に配列の最初の要素を基準値に選択し、その後基準値に基づいて配列を2つに分割します。その後、左右のサブ配列を再帰的にソートし、最終的に整列された配列が得られます。