Partially sorting an array, so that the last n elements are sorted?

Question

Is there a way to do partial sorting by data array to sort the last n items? In a good way, I mean using a standard library that does not implement my own sorting function (this is what I'm doing right now). Output example (using a smaller comparator):

2 1 4 || 5 6 8 10

Elements after || more elements than elements before || but only sorting the items to the right of || guaranteed (indices closer to the end of the array).

This is basically a change to the std :: partial_sort function, which sorts the left (first) elements.

Answer 1

Use std::partial_sort with reverse iterators.

For instance:

 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

Another option instead of partial_sort with reverse iterators and std :: is more for comparison - use std::nth_element to separate the collection, then std :: sort to sort the section you are interested in:

 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();