C++ で選択ソートアルゴリズムを実装する
この記事では、C++ で選択ソートアルゴリズムを実装する方法について説明します。
C++ で std::vector コンテナの選択ソートを実装する
単純なソートアルゴリズムの中で、選択ソートは実装が最も簡単なものの 1つと見なすことができます。ただし、O(n2)の複雑さがあり、大きなベクトルではまったく非効率になります。
選択ソートは、次のルーチンとして指定できます。最初に、ベクトルで最小値を見つけ、それを最初の要素と交換します。次に、ポインターを 2 番目の要素に移動し、残りのサブベクトルから最小値を見つけて、2 番目の要素と交換します。ポインターを一度に 1 要素ずつ進めながら、ベクトルの残りの部分について前の手順を続けます。
選択ソートの別の説明は、入力ベクトルを 2つの部分に分割することを言うかもしれません L：最初はソートされたサブベクトルで、2 番目はソートされていない要素の残りのサブベクトルです（元の順序です）。ソートされたサブベクトルは指定されたベクトルに存在すると想定できないため、ソートされたサブベクトルとソートされていないサブベクトルの間の除数として最初の要素を選択する必要があります。したがって、最小値を開始位置の要素と交換し始めると。ベクトルは自然にソートされた部分とソートされていない部分に分割されます。
次の例では、std::vector オブジェクトへの参照を取得し、要素のインプレース変更を実行する selectionSort 関数を実装します。std::min_element アルゴリズムを利用して、各反復の最小値を見つけました。これは、初めてアルゴリズムをよりよく理解するのに役立ちます。
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
void selectionSort(vector<T> &vec) {
for (auto it = vec.begin(); it != vec.end(); ++it) {
std::swap(*it, *std::min_element(it, vec.end()));
}
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
selectionSort(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
出力：
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
または、selectionSort 関数を 2 番目の for ループで書き直して、各反復の残りのソートされていないサブベクトルの最小値を求めることもできます。このバージョンは、アルゴリズムの複雑さの分析に適しています。選択ソートアルゴリズムの実行時間は 2 次ですが、マージソートやヒープソートなどの O（n log n）アルゴリズムと比較して、小さいベクトルでは驚くほど効率的です。この場合は一定時間の操作である 1つの STL 関数 std::swap を引き続き使用していることに注意してください。コード例を簡潔にすると便利です。
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
void selectionSort(vector<T> &vec) {
for (auto it = vec.begin(); it != vec.end(); ++it) {
auto min = it;
for (auto i = it + 1; i != vec.end(); ++i) {
if (*i < *min) min = i;
}
std::swap(*it, *min);
}
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
selectionSort(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
出力：
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
