stable_partition и получение O (nlogn) перестановок

Question

В ru.cppreference.com мы видим, что std::stable_partition выполняет O (n) перестановки, если нам разрешено использовать дополнительную память.Это я вижу.Каждый раз, когда мы находим элемент в диапазоне, где наш предикат равен false, мы обмениваем его в другой буфер.В конце мы можем просто скопировать этот дополнительный буфер в конец нашей успешной части.[Я также предполагаю, что в этом случае stable_partition может быть реализовано только с помощью итераторов Forward]

Чего я не получаю, так это по ссылке: stable_partition выполняет O (nlogn) перестановок, самое большее, еслинам не разрешено использовать дополнительную память.Вот моя попытка.

#include <utility>

namespace cho {

    template <typename BidirIt, typename Pred>
    BidirIt stable_partition(BidirIt begin, BidirIt end, Pred p) {
        BidirIt next_p = begin;
        for(BidirIt it = begin; it != end; ++it) {
            if(it == begin && p(*it)) {
                next_p++;
                continue;
            }
            if(p(*it)) {
                std::swap(*next_p++, *it);

                // riplle back swapped element to keep stability
                BidirIt cur = it;
                do {
                    BidirIt prev = --cur; cur++;
                    std::swap(*cur--, *prev--);
                } while(cur != next_p);
            }
        }
        return next_p;
    }

    template <typename ForwardIt, typename Pred>
    ForwardIt partition(ForwardIt begin, ForwardIt end, Pred p) {
        ForwardIt next_p = begin;
        for(ForwardIt it = begin; it != end; ++it) {
            if(p(*it)) {
                std::swap(*next_p++, *it);
            }
        }
        return next_p;
    }
} 

В этом случае, я колеблюсь после обмена.Итак, если расстояние между двумя последовательными истинными случаями составляет k, я выполню k перестановки.Я думаю, что для моего алгоритма наихудший случай возникает, когда диапазон обратно разделен.Если есть p элементов, в которых предикат равен false, и n-p элементов, в которых предикат равен true, я получу O ((n - p) * p) перестановки.Я думал об этом, и я не мог видеть, как я могу получить худший случай O (nlogn).

Реализации в LLVM, я проверил, но не смог понять, как достигается O (nlogn) перестановка.

PS: Моя реализация может быть неправильной.Я проверил это с парой входов, но это все.

Answer 1

Думайте рекурсивно.

Если левая половина и правая половина устойчиво разделены, как в

0...01...10...01...1
     b    m    e

, то единственной оставшейся операцией является вращение диапазона b, e, в результате чего m где b были.Это займет O(n) свопов.Теперь думаем рекурсивно, и стабильные разбиения обеих половинок.Будет O(log n) уровней рекурсии, всего O(n log n) свопов.В общих чертах,

iter stable_partition(begin, end) {
    if (end - begin < 2)
        return;
    iter mid = begin + (end - begin) / 2;
    iter left_break = stable_partition(begin, mid);
    iter right_break = stable_partition(mid, end);
    return rotate(left_break, mid, right_break);
}

Конечно, вы должны тщательно продумать, что rotate должно вернуть.

Answer 2

Я не знаю C ++, поэтому я не смогу написать его для вас, но это кажется довольно тривиальным, если у вас есть стабильная реализация сортировки. Хорошо, эта реализация также должна была бы сортировать на месте, поскольку у вас есть требование не использовать дополнительную память. При условии, что существует такая реализация сортировки, просто отсортируйте элементы в соответствии со следующим отношением порядка:

R(x, y) =  0 if  p(x) ==  p(y)
R(x, y) = -1 if  p(x) && !p(y)
R(x, y) =  1 if !p(x) && p(y) 

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