Рассмотрим элемент std::vector v из N и рассмотрим, что первые элементы N уже были отсортированы с помощью n < N и где (N-n)/N очень мало:
Существует ли разумный способ использования алгоритмов STL для сортировки этого вектора быстрее, чем с полным std::sort(std::begin(v), std::end(v))?
EDIT: пояснение: (N-n) несортированные элементы должны быть вставлены в правильное положение в пределах n первых уже отсортированных элементов.
EDIT2: вопрос с бонусом: и как найти n? (что соответствует первому несортированному элементу)
void foo( std::vector<int> & tab, int n ) {
std::sort( begin(tab)+n, end(tab));
std::inplace_merge(begin(tab), begin(tab)+n, end(tab));
}
для редактирования 2
auto it = std::adjacent_find(begin(tab), end(tab), std::greater<int>() );
if (it!=end(tab)) {
it++;
std::sort( it, end(tab));
std::inplace_merge(begin(tab), it, end(tab));
}
Отсортируйте другой диапазон, а затем используйте std:: merge.
Оптимальным решением будет сортировка хвостовой части независимо, а затем выполнение слияния на месте, как описано здесь.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.5750
Алгоритм довольно запутан и обычно считается "не стоит усилий".
Конечно, с С++ вы можете легко использовать std::inplace_merge. Однако имя этого алгоритма очень вводит в заблуждение. Во-первых, нет гарантии, что std::inplace_merge действительно работает на месте. И когда это действительно на месте, нет никакой гарантии, что он не будет реализован как полноразмерный вид. На практике это сводится к тому, чтобы попробовать это и посмотреть, достаточно ли это для ваших целей.
Но если вы действительно хотите сделать это на месте и формально более эффективным, чем полный сорт, тогда вам придется его реализовать вручную. STL может помочь с несколькими алгоритмами утилиты, но он не предлагает твердых решений "всего нескольких вызовов стандартных функций".
Использование сортировки вставки на N - n последние элементы:
template <typename IT>
void mysort(IT begin, IT end) {
for (IT it = std::is_sorted_until(begin, end); it != end; ++it) {
IT insertPos = std::lower_bound(begin, it, *it);
IT endRotate = it;
std::rotate(insertPos, it, ++endRotate);
}
}
Timsort алгоритм сортировки - это гибридный алгоритм, разработанный Pythonista Tim Peters. Он оптимально использует уже отсортированные подсегменты в любом месте массива, в том числе и в начале. Хотя вы можете найти более быстрый алгоритм, если вы точно знаете, что, в частности, первые n элементов уже отсортированы, этот алгоритм должен быть полезен для общего класса проблем. Википедия описывает это как:
Алгоритм находит подмножества уже упорядоченных данных и использует это знание для более эффективного сортировки остатка.
В собственных словах Тима Петерса
У этого есть сверхъестественная производительность на многих виды частично упорядоченных массивов (требуется меньше, чем lg (N!)), и всего лишь N-1), но так же быстро, как предыдущая высоконагруженная модель данных Python гибрид на случайных массивах.
Полная информация описывается в этом недатированном текстовом документе Тимом Петерсом. Примеры находятся в Python, но Python должен быть вполне читабельным даже для людей, не знакомых с его синтаксисом.
Используйте std:: partition_point (или is_sorted_until), чтобы найти n. Тогда, если n-m мало, выполните сортировку вставки (линейный поиск + std:: rotate).
Я предполагаю, что ваш вопрос имеет две цели:
Учитывая эти цели, я настоятельно рекомендую эту конкретную оптимизацию, если вы не уверены в том, что это стоит того. Насколько я помню, std:: sort() реализует алгоритм быстрой сортировки, который почти так же быстро выполняется на предварительно заданном входе, как и для определения, если/насколько сильно сортируется вход.
Вместо вмешательства в std:: sort вы можете попробовать изменить структуру данных в отсортированную/приоритетную очередь.