Частично сортируемый массив, поэтому сортируются последние n элементов?

Есть ли способ выполнить частичную сортировку массива данных, чтобы отсортировать последние n элементов? Под хорошим я подразумеваю использование стандартной библиотеки, а не реализацию собственной функции сортировки (это то, что я делаю прямо сейчас). Пример вывода (с использованием меньшего компаратора):

2 1 4 || 5 6 8 10

Все элементы после || больше элементов, чем элементы до ||, но гарантированно будут отсортированы только элементы справа от || (индексы ближе к концу массива).

По сути, это обращение функции std::partial_sort, которая сортирует левые (первые) элементы.


c++ sorting standard-library
person helloworld922    schedule 15.01.2013    source источник

Ответы (2)


arrow_upward
13
arrow_downward

Используйте 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 << ' ';
person Benjamin Lindley    schedule 15.01.2013
comment
Я думаю, что ему также нужен другой компаратор, так что добавьте в микс std::greater. - person Sjoerd; 16.01.2013

arrow_upward
6
arrow_downward

Другой возможностью вместо partial_sort с обратными итераторами и std::greater для сравнения было бы использование 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();
person Jerry Coffin    schedule 16.01.2013
comment
из любопытства, есть ли какие-либо причины/случаи, которые я бы рассматривал для использования этого решения вместо обратных итераторов? - person helloworld922; 16.01.2013
comment
@helloworld922: Я вижу два. Во-первых, (по крайней мере, мне) он кажется намного более читабельным. Во-вторых, в большинстве случаев мы можем ожидать, что он будет более эффективным. С N = общий размер и M = размер для сортировки, partial_sort имеет сложность ~ O (N log M), где это имеет сложность ~ O (N + M log M). - person Jerry Coffin; 16.01.2013
comment
хм, интересно. Забавно, что они не реализовали бы частичную сортировку внутри, если бы она была потенциально быстрее. - person helloworld922; 16.01.2013
comment
@ helloworld922: Конечно, они могли бы - я только цитирую то, что требует от них стандарт. - person Jerry Coffin; 16.01.2013
comment
Я не уверен, что вы можете сказать, что в большинстве случаев мы можем ожидать, что это будет более эффективно. Вы должны рассмотреть, каковы общие варианты использования частичной сортировки. Основываясь на отсутствии данных, а только на интуиции, я должен предположить, что основной вариант использования частичной сортировки — это когда у вас есть большой объем данных N, но вы хотите найти M лучших элементов, где M намного меньше, чем N. Потому что по мере того, как M приближается к N, вы доходите до точки, когда вы можете просто выполнить полную сортировку. И в этих случаях, судя по моим тестам, partial_sort превосходит nth_element+sort, к черту гарантии стандартной сложности. - person Benjamin Lindley; 16.01.2013
comment
@BenjaminLindley: Вы, вероятно, правы: в большинстве случаев, вероятно, ситуация хотя бы немного преувеличена. - person Jerry Coffin; 16.01.2013