C++ で挿入ソートアルゴリズムを実装する
この記事では、C++ で挿入ソートアルゴリズムを実装する方法を示します。
C++ で std::vector コンテナの挿入ソートを実装する
このガイドでは、std::vector オブジェクトへの参照を取得し、その場でコンテンツを変更する別個の関数として挿入ソートを実装する方法を示します。挿入ソートは、ベクトル内の各要素を繰り返し処理します。現在の要素を前の要素と逆の順序で比較することにより、現在の位置より前のすべての要素が確実にソートされます。
一般に、比較の順序はアルゴリズムのパフォーマンスではそれほど重要ではありませんが、逆の順序を想定し、それに応じてコードを実装します。また、要素を昇順で並べ替えると仮定します。それでも、実際の場合、一般的なソートアルゴリズムは、カスタム比較関数を引数として取ることができるはずです。現在の要素が前の要素よりも小さい場合、比較操作によって要素が右にシフトされることがよくあることに注意してください。後者の操作は、別のネストされた for ループを使用して実装されます。このループは、間違った順序の要素に対して std::swap 関数を呼び出します。
次のコードスニペットには、外側の for ループが配列全体の走査を担当する insertionSort 関数が含まれています。次のステップには前の要素との比較が含まれるため、イテレータをベクトルの 2 番目の要素に初期化します。内側のループは、現在の要素から最初の要素まで反復して比較します。比較関数が true と評価した場合、ペアは交換されます。else 式は、少なくとも 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 insertionSort(vector<T> &vec) {
for (auto it = vec.begin() + 1; it != vec.end(); ++it) {
auto key = it;
for (auto i = it - 1; i >= vec.begin(); --i) {
if (*i > *key) {
std::swap(*i, *key);
key--;
} else {
break;
}
}
}
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
insertionSort(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
出力：
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
あるいは、while ループ構造を使用して insertionSort 関数を再実装することもできます。後者がユーザーにとってより読みやすい形式として好まれる場合です。2つのアルゴリズムは同様の実装ロジックに従い、どちらも std::swap 関数を使用して要素をシフトします。挿入ソートは、大規模なデータセットでは非常に非効率的なアルゴリズムであり、その平均パフォーマンスは O（n2）です。
挿入ソートは、選択ソートと呼ばれる別の 2 次アルゴリズムに似ています。それらは両方ともベクトルを反復処理します。n の反復後、最初の 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 insertionSort2(vector<T> &vec) {
auto iter = vec.begin() + 1;
while (iter != vec.end()) {
auto key = iter;
auto it = iter - 1;
while (it >= vec.begin() && *it > *key) {
std::swap(*it, *key);
key--;
it--;
}
iter++;
}
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
insertionSort2(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
出力：
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
挿入ソートは、現在の要素を先行するすべての要素と常に比較する必要がないため、他の O（n2）アルゴリズムと比較して実際にはより効率的です。一方、選択ソートでは、ソートされていないサブ配列内のすべての要素を常に検索して、最小（または最大）の要素を見つける必要があります。後者のクラスは比較演算子のオーバーロードを実装するため、std::string のベクトルで両方の insertionSort 関数の実装を利用できることに注意してください。次の例は、文字列ベクトルを使用した基本的な使用法を示し、ソートされた単語のリストを出力します。
#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 insertionSort(vector<T> &vec) {
auto iter = vec.begin() + 1;
while (iter != vec.end()) {
auto key = iter;
auto it = iter - 1;
while (it >= vec.begin() && *it > *key) {
std::swap(*it, *key);
key--;
it--;
}
iter++;
}
}
int main() {
vector<string> vec2 = {"highway", "song", "work",
"borland", "death", "woman"};
printVector(vec2);
insertionSort(vec2);
printVector(vec2);
return EXIT_SUCCESS;
}
出力：
highway; song; work; borland; death; woman;
borland; death; highway; song; woman; work;
