C++ でクイックソートアルゴリズムを実装する
この記事では、C++ でクイックソートアルゴリズムを実装する方法に関する複数の方法を示します。
std::vector コンテナのクイックソートを実装する
クイックソートは、現代のコードベースで使用されている最速の汎用ソートアルゴリズムの 1つです。これは、マージソートアルゴリズムと同様の分割統治法を利用しています。ただし、前者は一般にパーティショニングと呼ばれる操作に依存します。元のベクトルは、pivot と呼ばれる要素で分割されます。この要素は、前の小さな要素と後の大きな要素を区切ります。これらの比較は、ユーザーが選択する必要のあるピボット値に関連していることに注意してください。ピボット値の選択は、このアルゴリズムのパフォーマンスにとって重要な要素です。これについては、この記事の後半で分析します。この時点で、ピボット要素が元のベクトルの最初の要素であると仮定しましょう。ピボット選択の方法ができたら、ベクトルを 2つの小さなベクトルに分割して、その場で再帰的に並べ替えることができます。クイックソート操作は、開始位置が互いに交差するまでベクトルを複数回分割するという点で、マージソートに似ていることに注意してください。
次のサンプルコードは、呼び出されるたびに partitionVec 関数を呼び出す再帰的な sort 関数を使用してアルゴリズムを実装します。分割プロセスは、同じベクトルオブジェクト内の要素を交換することにより、線形時間で実行できます。後者の操作は、partitionVec 関数を使用して実装されます。この関数は、特定の方法で並べ替え関数としても機能します。
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
T partitionVec(vector<T> &vec, size_t start, size_t end) {
T pivot = vec.at(start);
auto lh = start + 1;
auto rh = end;
while (true) {
while (lh < rh && vec.at(rh) >= pivot) rh--;
while (lh < rh && vec.at(lh) < pivot) lh++;
if (lh == rh) break;
T tmp = vec.at(lh);
vec.at(lh) = vec.at(rh);
vec.at(rh) = tmp;
}
if (vec.at(lh) >= pivot) return start;
vec.at(start) = vec.at(lh);
vec.at(lh) = pivot;
return lh;
}
template <typename T>
void sort(vector<T> &vec, size_t start, size_t end) {
if (start >= end) return;
auto boundary = partitionVec(vec, start, end);
sort(vec, start, boundary);
sort(vec, boundary + 1, end);
}
template <typename T>
void quickSort(vector<T> &vec) {
sort(vec, 0, vec.size() - 1);
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
quickSort(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
出力：
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
クイックソートの実装における再帰レベルを調査する
クイックソートの平均時間計算量は O（n log n）であり、マージソートアルゴリズムと同等です。ただし、クイックソートアルゴリズムは、ピボットの選択方法に大きく依存することに注意してください。この場合、ベクトルの最初の要素であるピボット値を選択するために、単純なバージョンを選択しました。これにより、特定のシナリオで O(n2)を使用すると実行時間が非常に悪くなる可能性があります。実際には、ランダムピボットを選択すると、O（n log n）パフォーマンスが得られる可能性が高くなります。ただし、最大のパフォーマンスが必要な場合は、入力データに基づくピボットの選択方法に注意する必要があります。
sort 関数の各呼び出しをカウントする追加の関数引数を使用して、前のコードスニペットの再帰プロセスを観察できます。次の例では、サイズの異なる 2つのベクトルに対して同様のテストを実行し、対応する合計を出力します。再帰呼び出しの合計は、ベクトルサイズを次の関数-2n - 1 に関連付けていることに注意してください。ここで、n は要素の数を示します。
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
auto partitionVec(vector<T> &vec, size_t start, size_t end) {
T pivot = vec.at(start);
auto lh = start + 1;
auto rh = end;
while (true) {
while (lh < rh && vec.at(rh) >= pivot) rh--;
while (lh < rh && vec.at(lh) < pivot) lh++;
if (lh == rh) break;
T tmp = vec.at(lh);
vec.at(lh) = vec.at(rh);
vec.at(rh) = tmp;
}
if (vec.at(lh) >= pivot) return start;
vec.at(start) = vec.at(lh);
vec.at(lh) = pivot;
return lh;
}
template <typename T>
void sort(vector<T> &vec, size_t start, size_t end, int &level) {
if (start >= end) return;
auto boundary = partitionVec(vec, start, end);
sort(vec, start, boundary, ++level);
sort(vec, boundary + 1, end, ++level);
}
template <typename T>
void quickSort(vector<T> &vec, int &level) {
sort(vec, 0, vec.size() - 1, ++level);
}
int main() {
vector<int> vec3(100, 10);
vector<int> vec4(200, 10);
int recursion_level = 0;
quickSort(vec3, recursion_level);
cout << "level: " << recursion_level << endl;
recursion_level = 0;
quickSort(vec4, recursion_level);
cout << "level: " << recursion_level << endl;
return EXIT_SUCCESS;
}
出力：
level: 199
level: 399
