Сортировать вектор, используя функцию логического предиката за O (N) время

Question

В качестве примера предположим, что я хочу отсортировать вектор {1, 2, 3, 4, 5}, поместив четные числа слева и нечетные числа справа. Я могу разработать алгоритм, который делает это за O (N) время (показано ниже). У меня вопрос, существует ли алгоритм STL для чего-то вроде этого?

Мое (не очень общее или симпатичное) решение

#include <iostream>
#include <vector>

/**
 Sort a vector of integers according to a boolean predicate function

 Reorders the elements of x such that elements satisfying some condition
 (i.e. f(x) = true) are arranged to the left and elements not satisfying the
 condition (f(x) = false) are arranged to the right
 (Note that this sort method is unstable)

 @param x vector of integers
 */
void sort_binary(std::vector<int>& x, bool (*func)(int)){
    // Strategy:
    // Simultaneously iterate over x from the left and right ends towards
    // the middle. When one finds {..., false, ..., ..., true, ....},
    // swap those elements

    std::vector<int>::iterator it1 = x.begin();
    std::vector<int>::iterator it2 = x.end();
    int temp;

    while(it1 != it2){
        while(func(*it1) && it1 < it2){
            ++it1;
        }
        while(!func(*it2) && it1 < it2){
            --it2;
        }
        if(it1 != it2){
            // Swap elements
            temp = *it1;
            *it1 = *it2;
            *it2 = temp;
        }
    }
}

int main() {
    // Sort a vector of ints so that even numbers are on the
    // left and odd numbers are on the right
    std::vector<int> foo {1, 2, 3, 4, 5};
    sort_binary(foo, [](int x) { return x % 2 == 0; } );
    for(auto &x : foo) std::cout << x << " ";
}

Answer 1

Вы можете использовать std::partition()

Изменение порядка элементов в диапазоне [first, last) таким образом, что все элементы, для которых предикат p возвращает true, предшествуютэлементы, для которых предикат p возвращает false.Относительный порядок элементов не сохраняется.

сложность:

Точно N применений предиката.Не более N / 2 свопов, если ForwardIt соответствует требованиям LegacyBidirectionalIterator, и не более N свопов в противном случае.

std::partition( foo.begin(), foo.end(), [](int x) { return x % 2 == 0; } );

живой пример

PS вы можетеиспользуйте std::stable_partition(), если хотите сохранить порядок элементов