partial_sort: 部分的なソート
与えられた列の全要素をソートする必要はなく、例えば上位10個までが得られれば十分、なんてときに使われるのが partial_sort() です。partial_sort(first, mid, last) は 列[first,last) をソート対象とし, [first, mid) にソート列を作ります。従って例えば配列 a[N] の中から小さい順に10個を得たいなら、partial_sort(a, a+10, a+N); となります。
const int N = 100;
array<int,N> ar;
iota(ar.begin(), ar.end(), 0);
random_shuffle(ar.begin(), ar.end());
// partial_sort: 10個ずつソート
for (auto first = ar.begin(); first != ar.end(); advance(first,10) ) {
auto last = first;
advance(last,10);
partial_sort(first,last,ar.end());
for_each(first, last, [](int x) { cout << setw(3) << x;});
cout << endl;
}
cout << endl;
partial_sort() のバリエーションとして partial_sort_copy() が用意されています。こいつは入力列の入れ替え/書き換えを一切行わずに部分ソートのコピーを生成します。入力列からの要素の読み込みは入力順に一度しか行われないので、入力列としてストリームを与えることも可能です。
// partial_sort_copy: ストリームを対象に要素数5の部分ソートを行う
istringstream stream("1 3 5 7 9 10 15 11 14 12 13 8 6 4 2 0");
istream_iterator<int> first(stream);
istream_iterator<int> last;
array<int,5> result;
partial_sort_copy(first, last, result.begin(), result.end());
for_each(result.begin(), result.end(), [](int n) { cout << n << ' ';});
sort_heap
sort_heap() はちょっと（かなり?）特殊なソート・アルゴリズム。ヒープ化された列をソートします。sort_heap() はその呼び出しに先立って push_heap() もしくは make_heap() を使ってヒープを構築しておかなければなりません。
auto greater = [](int x, int y) { return x > y;};
vector<int> v;
istringstream stream("1 3 5 7 9 10 15 11 14 12 13 8 6 4 2 0");
istream_iterator<int> first(stream);
istream_iterator<int> last;
// push_heapによるヒープの構築
while ( first != last ) {
v.push_back(*first);
push_heap(v.begin(), v.end(), greater);
++first;
}
// しかるのちsort_heap
sort_heap(v.begin(), v.end(), greater);
for_each(v.begin(), v.end(), [](int n) { cout << n << ' ';});
cout << endl << endl;
random_shuffle(v.begin(), v.end());
// make_heapによるヒープの構築
make_heap(v.begin(), v.end(), greater);
// しかるのちsort_heap
sort_heap(v.begin(), v.end(), greater);
for_each(v.begin(), v.end(), [](int n) { cout << n << ' ';});
cout << endl;
...<algorithm> が提供するソート系関数群はこれでおおむね列挙できたかな。「忘れもの」がございましたらご一報くださいませ。
