c++ - 最後のn要素がソートされるように配列を部分的にソートしますか?

Question

最後の n 要素がソートされるように、データの配列に対して部分ソートを実行する方法はありますか? 良いとは、独自のソート機能を実装するのではなく、標準ライブラリを使用することを意味します (これは私が現在行っていることです)。出力例 (less コンパレータを使用):

2 1 4 || 5 6 8 10

後の要素||はすべて、前の要素よりも大きくなりますが、 (配列の末尾に近いインデックス)||の右側の要素のみが並べ替えられることが保証されます。||

これは基本的に、左 (最初) の要素をソートする std::partial_sort 関数の逆です。

Answer 1

std::partial_sort逆反復子で使用します。

例えば：

int x[20];
std::iota(std::begin(x), std::end(x), 0);
std::random_shuffle(std::begin(x), std::end(x));

std::reverse_iterator<int*> b(std::end(x)),
                            e(std::begin(x));
std::partial_sort(b, b+10, e, std::greater<int>());
for (auto i : x)
    std::cout << i << ' ';

Answer 2

partial_sort逆イテレータとstd::の代わりにstd::nth_element、コレクションをパーティション化するために使用することもできます。次に、std :: sortを使用して、関心のあるパーティションをソートします。

std::vector<int> data{5, 2, 1, 6, 4, 8, 10}; //  your data, shuffled

std::nth_element(data.begin(), data.begin()+2, data.end());

std::sort(data.begin()+2, data.end();