とくにあぶなくないRiSKのブログ

危ないRiSKのブログだったかもしれない。本当はRiSKだけどググラビリティとか取得できるIDの都合でsscriskも使ったり。

std::sort, std::stable_sort, std::partial_sort

STL―標準テンプレートライブラリによるC++プログラミング 第2版
私の環境において下に書いた実験コードでは sort も安定したソートをしているように見える。でも,本当に安定なソートがほしいなら stable_sort 使うべし。

// P106 ex05-22.cpp
#include<iostream>
#include<vector>
#include<algorithm>
template<typename T>
struct Mod10Less{
 bool operator()(const T& x, const T& y){return x % 10 < y % 10;}
};
int main(){
 using std::cout;
 using std::endl;
 using std::vector;
 using std::ostream_iterator;
 using std::sort;
 using std::stable_sort;
 using std::partial_sort;
 cout << "Illustrating the generic sort, stable_sort, "
  "and partial_sort algorithms." << endl;
 vector<int> v0;
 const int N = 20;
 for(int i = 0; i < N; ++i)
  v0.push_back(i);
 vector<int> v(v0);
 ostream_iterator<int> o(cout, " ");

 cout << "Before sorting:\n";
 copy(v.begin(), v.end(), o); cout << endl;

 sort(v.begin(), v.end(), Mod10Less<int>());
 cout << "After sorting by last digits with sort:\n";
 copy(v.begin(), v.end(), o); cout << endl;

 v = v0;
 stable_sort(v.begin(), v.end(), Mod10Less<int>());
 cout << "After stable_sort by last digits with sort:\n";
 copy(v.begin(), v.end(), o); cout << endl;

 v = v0;
 partial_sort(v.begin(), v.begin() + 5, v.end(), Mod10Less<int>());
 cout << "After sorting whith partial_sort to get\n"
  "5 values with smallest last digits:\n";
 copy(v.begin(), v.end(), o); cout << endl;
}

出力例:

Illustrating the generic sort, stable_sort, and partial_sort algorithms.
Before sorting:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
After sorting by last digits with sort:
0 10 1 11 2 12 3 13 4 14 5 15 6 16 7 17 8 18 9 19
After stable_sort by last digits with sort:
0 10 1 11 2 12 3 13 4 14 5 15 6 16 7 17 8 18 9 19
After sorting whith partial_sort to get
5 values with smallest last digits:
10 0 1 11 2 5 6 7 8 9 4 3 12 13 14 15 16 17 18 19