クイックソートを理解する

学生時代に習ったソートアルゴリズムを改めてまとめたものとなります

クイックソートって？

ソートアルゴリズムの1つでソートアルゴリズムの中で処理速度が一番速いものとなっています。ただ、条件などによっては他のソートアルゴリズムの方が速い場合があります。詳しくは以下のサイトがわかりやすいと思います

ソート用の配列を生成する

ソートの動作確認用に1～100までのランダムな数字を持つ配列を生成します

std::vector<int> RandomCreate() {
    std::set<int> uniqueNumbers; // 重複を防ぐためにstd::setを使用
    std::vector<int> numberArray; // 返却用変数

    // 乱数生成器の初期化
    std::random_device rd;
    std::mt19937 gen(rd());

    // 1から100までのランダムな数字を生成
    std::uniform_int_distribution<int> distribution(1, 100);

    while (uniqueNumbers.size() < 10) {
        int randomNumber = distribution(gen);

        // 重複を防ぐために挿入前に確認
        if (uniqueNumbers.find(randomNumber) == uniqueNumbers.end()) {
            uniqueNumbers.insert(randomNumber);
        }
    }

    // 生成したランダムな数字を表示
    std::cout << "Unique Random Numbers: ";
    for (int number : uniqueNumbers) {
        std::cout << number << " ";
        // 返却用変数に代入する
        numberArray.push_back(number);
    }
    std::cout << std::endl;

    // ランダムにシャッフルする
    std::shuffle(numberArray.begin(), numberArray.end(), gen);

    return numberArray;
}

ランダムな数字が生成されて、順番もいい感じにばらけました

クイックソートを実装する

それでは実際にクイックソートをC＋＋で実装してみます

template <typename T>
void QuickSort(std::vector<T>& arr, int low, int high) {
    if (low < high) {
        // arr[pi] は現在の基準値の位置
        int pi = partition(arr, low, high);

        std::cout << "Midway Array(quickSort): ";
        for (int i : arr) {
            std::cout << i << " ";
        }
        std::cout << std::endl;

        // 基準値を基に再帰的にソートを行う
        quickSort(arr, low, pi - 1);
        std::cout << "Midway Array(quickSort): ";
        for (int i : arr) {
            std::cout << i << " ";
        }
        std::cout << std::endl;

        quickSort(arr, pi + 1, high);
        std::cout << "Midway Array(quickSort): ";
        for (int i : arr) {
            std::cout << i << " ";
        }
        std::cout << std::endl;
    }
}

まずは再帰的に呼び出す関数を用意します。配列の入れ替えを実施する関数は別で用意します

template <typename T>
int Partition(std::vector<T>& arr, int low, int high) {
    T pivot = arr[high];  // 基準値を最後の要素とする
    int i = low - 1;

    for (int j = low; j <= high - 1; j++) {
        // 現在の要素が基準値以下であれば、i をインクリメントし、要素を swap する
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }

    // 基準値を正しい位置に移動し、その位置を返す
    std::swap(arr[i + 1], arr[high]);

    std::cout << "Midway Array(partition): ";
    for (int i : arr) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return i + 1;
}

最期に配列の中身を入れ替える関数を実装します

実際に動かしてみる

検証用の配列を作成し、それをクイックソートで並び替えて結果を見てみましょう

std::vector<int> arr = RandomCreate();
int n = arr.size();

std::cout << "Original Array: ";
for (int i : arr) {
    std::cout << i << " ";
}
std::cout << std::endl;

quickSort(arr, 0, n - 1);

std::cout << "Sorted Array: ";
for (int i : arr) {
    std::cout << i << " ";
}
std::cout << std::endl;

クイックソートを用いて配列が並び変えられていることが確認できました