C++のstable_sort（STL stable_sort）ソートアルゴリズムの仕組み

2年 ago
芽依, 雨夜
1 minute

stable_sortは、C++標準ライブラリに提供されているソートアルゴリズムの一種であり、コンテナ内の要素をソートして同値な要素の相対的な位置が変わらないようにします。つまり、2つの要素がソート前に同値であれば、ソート後でも同値のままです。

安定ソート的时间計算量は、要素数Nに対してO(NlogN)です。これは分治の手法を採用しており、まず対象を2つの部分列に分割し、それぞれをソートした後、最後に2つの部分をマージします。このとき、同じ要素があった場合、元の位置が前の要素を優先して採用することで、同値要素の相対位置関係を保持できます。

一般的にstable_sortでは、具体的にはマージソートアルゴリズムを採用しています。マージソートは、コンテナを断続的に二分割し、各サブシーケンスに1つの要素だけの状態にしてから、それらのサブシーケンスを2つずつマージし、最終的にソートされたシーケンスを得ています。マージの処理では、一時的な結果を格納するために余分なメモリ領域を使用する必要があります。

stable_sortを使うにはヘッダーファイルのインクルードが必要で、関数テンプレートを呼び出すことでソートを行う。関数テンプレートの定義は以下の通りだ。

隙間に入る

安定ソート(std::stable_sort)

firstとlastはそれぞれ格納されている要素の開始位置と終了位置を示し、それらはランダムアクセスイテレータである必要があります。stable_sortは[first, last)範囲内の要素をソートします。

stable_sort を使う例を以下に示します。

#include <iostream>
#include <algorithm>
#include <vector>
int main() {
std::vector<int> nums = {5, 2, 8, 1, 9, 3, 7, 4, 6};
std::stable_sort(nums.begin(), nums.end());
for(int num : nums) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}

1 2 3 4 5 6 7 8 9

この例では、stable_sortを使用してベクタコンテナ内の要素を並べ替えます。最終的な出力の結果は、順序付けられたシーケンスです。

bannerAds