C++で配列を昇順に並べ替える方法｜クイックソートの実装をわかりやすく解説

整数型の配列が与えられ、その要素を昇順に並べ替えることを考えます。たとえば、配列が [5,2,3,1] であれば、結果は [1,2,3,5] となります。

この問題はクイックソートのアルゴリズムを使うことで効率的に解けます。クイックソートは平均計算量 O(n log n) の高速なソート手法で、基準値（ピボット）を軸に配列を分割しながら、再帰的に整列を進めていくのが特徴です。

解決のための手順

• partition（分割）メソッドを作成します。引数として配列・low・high を受け取ります。

• pivot := low と初期化します。

• i を low から high - 1 まで繰り返します。
  　・nums[i] < nums[high] の場合、nums[i] と nums[pivot] を入れ替え、pivot を 1 増やします。

• ループ終了後、nums[pivot] と nums[high] を入れ替えます。

• sortArr() メソッドを定義します。こちらも配列・low・high を引数に取ります。

• low >= high の場合は何もせずに return します。

• partitionIndex := partition(nums, low, high) を呼び出します。

• sortArr(nums, low, partitionIndex - 1) を再帰的に呼び出します。

• sortArr(nums, partitionIndex + 1, high) を再帰的に呼び出します。

• main 関数から、low = 0、high = 配列サイズ - 1 を渡して sortArr() を呼び出します。

それでは、実際の実装を見ながら理解を深めましょう。

実装例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<string> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    int partition(vector <int>& nums, int low, int high){
        int pivot = low;
        for(int i = low; i < high; i++){
            if(nums[i] < nums[high]){
                swap(nums[i], nums[pivot]);
                pivot++;
            }
        }
        swap(nums[pivot], nums[high]);
        return pivot;
    }
    void sortArr(vector <int>& nums, int low, int high){
        if(low >= high) return;
        int partitionIndex = partition(nums, low, high);
        sortArr(nums, low, partitionIndex - 1);
        sortArr(nums, partitionIndex + 1, high);
    }
    vector<int> sortArray(vector<int>& nums) {
        sortArr(nums, 0, nums.size() - 1);
        return nums;
    }
};
main(){
    vector<int> v1 = {5,2,3,1};
    Solution ob;
    print_vector(ob.sortArray(v1));
}

入力

[5,2,3,1]

出力

[1,2,3,5]

このプログラムでは、partition 関数がピボットより小さい要素を配列の左側に集め、最後にピボットを正しい位置へ移動させます。続いて sortArr 関数が、ピボットの左右それぞれの部分配列に対して同じ処理を再帰的に適用することで、配列全体が昇順に整列されます。