C++ 標準テンプレートライブラリ（STL）での並べ替え
-
C++ で
sort()関数を使用して配列または STL コンテナをソートする - C++ で配列を降順で並べ替える
-
C++ で
partial_sort()関数を使用して配列またはベクトルの一部を並べ替える -
C++ で
sort()関数を使用したユーザー定義またはカスタムソート -
C++ で
is_sorted()メソッドを使用する - ソートアルゴリズムの時間複雑性
このチュートリアルでは、sort() と呼ばれる広く使用されている C++ 関数について学習します。また、並べ替えに関連する他の機能についても見ていきます。
C++ でデータを並べ替えるには、アルゴリズムを記述してデータに適用するか、C++ STL にある組み込み関数 sort() を使用できます。sort() 関数は、algorithm ヘッダーファイルで定義されています。
この関数は、実行時間を最小限に抑えるために、クイックソート、ヒープソート、および挿入ソートの 3つのソートアルゴリズムを使用するハイブリッドソートアルゴリズムである IntroSort アルゴリズムを使用します。
この関数は、指定された範囲の要素を並べ替えます。
構文：
sort(start iterator, end iterator, compare_function)
これにより、開始イテレータと終了イテレータで定義された範囲の要素が、デフォルトで昇順で並べ替えられます（これがデフォルトの compare_function です）。
C++ で sort() 関数を使用して配列または STL コンテナをソートする
並べ替えは、データに対して実行される基本的な操作の 1つです。データの増加、減少、またはユーザー定義（カスタムソート）の方法でデータを配置します。
sort() 関数を使用して、C++ で配列またはベクトル、セット、マップなどの STL コンテナを並べ替えることができます。
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};
// array size
int n = sizeof(arr) / sizeof(arr[0]);
vector<int> v{35, 67, 11, -9, 7, -22}; // vector
cout << "The array after sorting is : \n";
sort(arr, arr + n);
sort(v.begin(), v.end()); // sorting vector
for (int i = 0; i < n; ++i) cout << arr[i] << " ";
cout << endl;
cout << "The vector after sorting is : \n";
for (int i = 0; i < v.size(); ++i) cout << v[i] << " ";
}
出力：
The array after sorting is :
0 1 2 3 4 5 6 7 8 9
The vector after sorting is :
-22 -9 7 11 35 67
デフォルトでは、アイテムは昇順で配置されます。
C++ で配列を降順で並べ替える
C++ STL に存在する配列またはコンテナーを降順でソートするには、sort() 関数で greater<type>() と呼ばれる 3 番目のパラメーターを渡す必要があります。この関数は、最後の要素が降順でソートされるように比較を実行します。
タイプは、使用している配列またはコンテナのタイプ、int、float、または文字列型を指します。
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};
// array size
int n = sizeof(arr) / sizeof(arr[0]);
vector<int> v{35, 67, 11, -9, 7, -22}; // vector
cout << "The array after sorting is : \n";
sort(arr, arr + n, greater<int>());
sort(v.begin(), v.end(), greater<int>()); // sorting vector
for (int i = 0; i < n; ++i) cout << arr[i] << " ";
cout << endl;
cout << "The vector after sorting is : \n";
for (int i = 0; i < v.size(); ++i) cout << v[i] << " ";
}
出力：
The array after sorting is :
9 8 7 6 5 4 3 2 1 0
The vector after sorting is :
67 35 11 7 -9 -22
C++ で partial_sort() 関数を使用して配列またはベクトルの一部を並べ替える
partial_sort() を使用して、配列の一部だけを並べ替えることができます。この方法は、元の並べ替え方法のバリアントに他なりません。
構文：
partial_sort(first, middle, last)
範囲（first、last）の要素を再配置して、中央より前の要素が昇順で並べ替えられ、中央より後の要素が特定の順序なしで残されるようにします。
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
vector<int> vr{35, 67, 11, -9, 7, -22}; // vector
cout << "The vector after partial sorting is : \n";
partial_sort(vr.begin(), vr.begin() + 2, vr.end());
for (int i = 0; i < vr.size(); ++i) cout << vr[i] << " ";
}
出力：
The vector after partial sorting is :
-22 -9 67 35 11 7
最初の 2つの要素のみがソートされ、残りはランダムな順序で存在していることがわかります。
C++ で sort() 関数を使用したユーザー定義またはカスタムソート
データを昇順または降順で並べ替える場合は、この関数を使用できますが、ユーザー定義の方法でデータを並べ替えたい場合があります。
ここでは、カスタムの並べ替え関数を作成する必要があります。これは、sort() 関数の 3 番目のパラメーターとして渡します。
#include <algorithm>
#include <iostream>
using namespace std;
bool myfunction(string x, string y) { return x.size() < y.size(); }
int main() {
string str[] = {"a", "abc", "ba", "abcd"};
int n = 4;
sort(str, str + n); // normal sort function
cout << "Array after sorting : \n";
for (int i = 0; i < n; ++i) cout << str[i] << " ";
cout << endl;
sort(str, str + n, myfunction);
cout << "Array after user defined sorting : \n";
for (int i = 0; i < n; ++i) cout << str[i] << " ";
}
出力：
Array after sorting :
a abc abcd ba
Array after user defined sorting :
a ba abc abcd
最初の sort メソッドは、デフォルトで文字列の配列を辞書式順序で並べ替えます。2 番目の並べ替えメソッドは、文字列の長さに基づいて文字列を並べ替えます。つまり、myfunction という名前のカスタム比較関数で説明した条件です。
C++ で is_sorted() メソッドを使用する
指定された範囲のデータがソートされているかどうかを確認する場合は、この方法を使用できます。
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
vector<int> v{35, 67, 11, -9, 7, -22}; // vector
cout << is_sorted(v.begin(), v.end());
}
出力：
0
ベクトルはソートされていないため、出力は 0、つまり false として取得されます。
ソートアルゴリズムの時間複雑性
sort() の時間計算量は O(NlogN) です。ここで、N は sort() 関数が適用される要素の数です。
