partial_sortによる部分ソート

http://www.geocities.jp/ky_webid/cpp/library/019.html

partial_sort関数を使えば、例えば先頭からｎ個までがソートされた時点で処理を中断するといったことができます。

実例を見たほうが早いですね。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main () {
    vector<int> data;
    
    data.push_back(9);
    data.push_back(4);
    data.push_back(2);
    data.push_back(3);
    data.push_back(1);
    data.push_back(5);
    data.push_back(7);
    data.push_back(8);
    data.push_back(6);
    
    // 4個目までソートする
    partial_sort(data.begin(),data.begin()+4,data.end());
    
    copy(data.begin(),data.end(),ostream_iterator<int>(cout,"\n"));
    
    return 0;
}

$ main
1
2
3
4
9
5
7
8
6

上から4つ目前ではソートされていますね。

上記のように書くと4つ目までソートした時点で処理を中断します。

データの多いリスト等で小さな値から順に10個まで欲しいだけなのに全部ソートしなければならないのは微妙なんていうときに使えそうですね。