Частично сортируемый массив, так что последние n элементов отсортированы?
Есть ли способ выполнить частичную сортировку массива данных, чтобы отсортировать последние n элементов? Под «хорошей» я подразумеваю использование стандартной библиотеки, а не реализацию собственной функции сортировки (это то, чем я сейчас занимаюсь).
Пример вывода (используя меньше компаратора):
2 1 4 || 5 6 8 10
Элементы после || все больше, чем элементы, прежде чем элементы ||, но только элементы справа от || (индексы ближе к концу массива) гарантированно будут отсортированы.
По сути, это обращение к функции std :: part_sort, которая сортирует левые (первые) элементы.
Решение
использование 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 << ' ';
Другие решения
Другая возможность вместо 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();