Сортировка вектора, в котором n первых элементов уже отсортированы?

Рассмотрим элемент 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? (что соответствует первому несортированному элементу)

Ответ 1

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

Ответ 2

Отсортируйте другой диапазон, а затем используйте std:: merge.

Ответ 3

Оптимальным решением будет сортировка хвостовой части независимо, а затем выполнение слияния на месте, как описано здесь.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.5750

Алгоритм довольно запутан и обычно считается "не стоит усилий".

Конечно, с С++ вы можете легко использовать std::inplace_merge. Однако имя этого алгоритма очень вводит в заблуждение. Во-первых, нет гарантии, что std::inplace_merge действительно работает на месте. И когда это действительно на месте, нет никакой гарантии, что он не будет реализован как полноразмерный вид. На практике это сводится к тому, чтобы попробовать это и посмотреть, достаточно ли это для ваших целей.

Но если вы действительно хотите сделать это на месте и формально более эффективным, чем полный сорт, тогда вам придется его реализовать вручную. STL может помочь с несколькими алгоритмами утилиты, но он не предлагает твердых решений "всего нескольких вызовов стандартных функций".

Ответ 4

Использование сортировки вставки на 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);
    }
}

Ответ 5

Timsort алгоритм сортировки - это гибридный алгоритм, разработанный Pythonista Tim Peters. Он оптимально использует уже отсортированные подсегменты в любом месте массива, в том числе и в начале. Хотя вы можете найти более быстрый алгоритм, если вы точно знаете, что, в частности, первые n элементов уже отсортированы, этот алгоритм должен быть полезен для общего класса проблем. Википедия описывает это как:

Алгоритм находит подмножества уже упорядоченных данных и использует это знание для более эффективного сортировки остатка.

В собственных словах Тима Петерса

У этого есть сверхъестественная производительность на многих виды частично упорядоченных массивов (требуется меньше, чем lg (N!)), и всего лишь N-1), но так же быстро, как предыдущая высоконагруженная модель данных Python гибрид на случайных массивах.

Полная информация описывается в этом недатированном текстовом документе Тимом Петерсом. Примеры находятся в Python, но Python должен быть вполне читабельным даже для людей, не знакомых с его синтаксисом.

Ответ 6

Используйте std:: partition_point (или is_sorted_until), чтобы найти n. Тогда, если n-m мало, выполните сортировку вставки (линейный поиск + std:: rotate).

Ответ 7

Я предполагаю, что ваш вопрос имеет две цели:

улучшить время выполнения (используя умный способ)
с небольшим усилием (ограничение на STL)

Учитывая эти цели, я настоятельно рекомендую эту конкретную оптимизацию, если вы не уверены в том, что это стоит того. Насколько я помню, std:: sort() реализует алгоритм быстрой сортировки, который почти так же быстро выполняется на предварительно заданном входе, как и для определения, если/насколько сильно сортируется вход.

Вместо вмешательства в std:: sort вы можете попробовать изменить структуру данных в отсортированную/приоритетную очередь.