CODEWITHSUNDEEP
c++sortingstl
Ben
Ben

Reputation: 21645

Sort a vector using a boolean predicate function in O(N) time

As an example, suppose I want to sort the vector {1, 2, 3, 4, 5}, placing even numbers on the left and odd numbers on the right. I can devise an algorithm that does this in O(N) time (shown below). My question is, is there an existing STL algorithm for something like this?

My (not very generic or pretty) solution

#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 << " ";
}

Upvotes: 2

Views: 358

Answers (1)

Slava
Slava

Reputation: 44268

You can use std::partition()

Reorders the elements in the range [first, last) in such a way that all elements for which the predicate p returns true precede the elements for which predicate p returns false. Relative order of the elements is not preserved.

complexity:

Exactly N applications of the predicate. At most N/2 swaps if ForwardIt meets the requirements of LegacyBidirectionalIterator, and at most N swaps otherwise.

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

live example

PS you can use std::stable_partition() if you want to preserve order of the elements

Upvotes: 4

Related Questions