C++ でマージソートアルゴリズムを実装する
この記事では、C++ でマージソートアルゴリズムを実装する方法を紹介します。
C++ で std::vector コンテナのマージソートを実装する
マージソートは、分割統治戦略を利用して効率を高め、大きなリストの汎用ソートアルゴリズムとして使用できます。アルゴリズムの背後にある考え方は、入力ベクトルを複数の小さなベクトルに分割し、それらの各ベクトルを並べ替えることです。小さいベクトルが完成したら、それらを 1つのリストにマージできます。これは、たまたま比較的簡単な操作です。次のコード例は、このソリューションに最適であるため、再帰を使用してこのメソッドを実装していることに注意してください。再帰的プロセスを使用して、比較関数が呼び出される 2 要素のベクトルを取得するまで、元のベクトルを複数回分割します。各ペアがソートされると、再帰の最終レベルが戻るまで、4 要素のベクトルなどにマージされます。
mergeSort 関数は、再帰的プロセスの中核部分です。唯一の引数としてベクトル参照を取り、サイズが 1 以下であるかどうかをチェックします。その場合、ベクトルはソートされたものとして適格であり、関数は戻ります。ベクターに 2つ以上の要素が含まれている場合、ベクターは 2つの別個のベクターオブジェクトに分割され、それぞれで mergeSort 関数が呼び出されます。後者の部分では、ソートが最小のサブベクトルから開始されることに注意してください。再帰がそのようなレベルに達すると、両方の mergeSort 関数が戻り、次のコードが実行を開始します。最初に、vec ベクトルがクリアされ、次に merge 関数が呼び出されます。merge 機能は、綿密な観察でグロックできる反復プロセスで実装されます。一般に、後者のステップでは、ソートされた最小のベクトルを 1つのベクトルオブジェクトに結合します。
#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>
void merge(vector<T> &vec, vector<T> &v1, vector<T> &v2) {
auto siz1 = v1.size();
auto siz2 = v2.size();
size_t p1 = 0;
size_t p2 = 0;
while (p1 < siz1 && p2 < siz2) {
if (v1.at(p1) < v2.at(p2))
vec.push_back(v1.at(p1++));
else
vec.push_back(v2.at(p2++));
}
while (p1 < siz1) vec.push_back(v1.at(p1++));
while (p2 < siz2) vec.push_back(v2.at(p2++));
}
template <typename T>
void mergeSort(vector<T> &vec) {
if (vec.size() <= 1) return;
auto iter = vec.begin() + vec.size() / 2;
vector<T> v1(vec.begin(), iter);
vector<T> v2(iter, vec.end());
mergeSort(v1);
mergeSort(v2);
vec.clear();
merge(vec, v1, v2);
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
mergeSort(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
出力：
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
あるいは、STL std::merge アルゴリズムを使用して前のコードを書き直すこともできます。これにより、コードの読み取りが簡素化されます。std::merge 関数は merge 実装の代わりになり、ベクトルのマージは mergeSort 関数本体の 1つのステートメントで実行できることに注意してください。再帰の最終レベルが mergeSort の最初の呼び出しで 2つのベクトルを返す場合、std::merge の最後の呼び出しは、main 関数から観察できる元の vec オブジェクトにソートされたコンテンツを格納します。
#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>
void mergeSort2(vector<T> &vec) {
if (vec.size() <= 1) return;
auto iter = vec.begin() + vec.size() / 2;
vector<T> v1(vec.begin(), iter);
vector<T> v2(iter, vec.end());
mergeSort2(v1);
mergeSort2(v2);
vec.clear();
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(),
std::back_inserter(vec));
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
mergeSort2(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
経験的なタイミング測定によるマージソートの複雑さの分析
マージソートは、O（n log n）の最悪の場合の実行時間を提供します。これは、現代の汎用ソートアルゴリズムの中でたまたま最高の 1つです。最悪のシナリオでは、クイックソートアルゴリズムが提供する以上の線形空間の複雑さがあります。後者は、実装がピボット変数を選択するための効率的な方法を利用する場合、実際には比較的高速になる傾向があります。
再帰的な方法を理解するのはかなり難しいかもしれませんが、各ステップの要点に飛び込むためにいつでもデバッガーを使用できます。ただし、より高いレベルでは、次のコードサンプルを使用して、異なるベクトルサイズ間の再帰関数呼び出しをカウントできます。再帰呼び出しの合計は関数-2n - 2 になる傾向があることに注意してください。ここで、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>
void mergeSort2(vector<T> &vec, int &level) {
if (vec.size() <= 1) return;
auto iter = vec.begin() + vec.size() / 2;
vector<T> v1(vec.begin(), iter);
vector<T> v2(iter, vec.end());
mergeSort2(v1, ++level);
mergeSort2(v2, ++level);
vec.clear();
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(),
std::back_inserter(vec));
}
int main() {
vector<int> vec3(100, 10);
vector<int> vec4(200, 10);
int recursion_level = 0;
mergeSort2(vec3, recursion_level);
cout << "recursion level: " << recursion_level << endl;
recursion_level = 0;
mergeSort2(vec4, recursion_level);
cout << "recursion level: " << recursion_level << endl;
return EXIT_SUCCESS;
}
出力：
recursion level: 198
recursion level: 398
