Partition Algorithm

Introduction

Partition algorithm is one of my favorite $O(N)$ algorithms as it is efficient and extremely useful in practice. It is also a fundamental building block for sorting algorithms such as Quicksort and partial sort, and linear-time worst-case selection algorithm.

In this blog post, I would like to quickly discuss the partition algorithm.

Partition Algorithm

Custom Two-Pointer Approach

partition.cpp

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

template <class ForwardIt, class UnaryPredicate>
constexpr ForwardIt custom_partition(ForwardIt first, ForwardIt last,
                                     UnaryPredicate p)
{
    // Two-pointer approach
    if (first == last)
    {
        return first;
    }
    --last;
    while (first != last)
    {
        while (first != last && p(*first))
        {
            ++first;
        }
        while (first != last && !p(*last))
        {
            --last;
        }
        // Swap values
        std::swap(*first, *last);
    }
    return first;
}

int main()
{
    std::vector<int> v{0, 55, 66, 77, 11, 22, 33, 44, 88, 99};
    int const pivot{60};
    std::cout << "Original Vector:" << std::endl;
    std::copy(std::begin(v), std::end(v),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
    auto it = custom_partition(std::begin(v), std::end(v),
                               [pivot](int const n) { return n < pivot; });

    std::cout << "Pivot: " << pivot << std::endl;
    std::cout << "Partitioned Vector:" << std::endl;
    std::copy(std::begin(v), it, std::ostream_iterator<int>(std::cout, " "));
    std::cout << " * "
              << " ";
    std::copy(it, std::end(v), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
    auto const num_items_left{std::distance(std::begin(v), it)};
    auto const num_items_right{std::distance(it, std::end(v))};
    std::cout << "Number of Items Left: " << num_items_left << std::endl;
    std::cout << "Number of Items Right: " << num_items_right << std::endl;
}

$ g++ partition.cpp -o partition --std c++14
$ ./partition
Original Vector:
0 55 66 77 11 22 33 44 88 99
Pivot: 60
Partitioned Vector:
0 55 44 33 11 22  *  77 66 88 99
Number of Items Left: 6
Number of Items Right: 4

C++ Standard Library Function

C++ standard library has provided the standard partition function std::partition for us. So instead of using the custom_partition function we implemented in the above example, we could just use std::partition.

The possible implementation suggested by CPP Reference is as follows.

template <class ForwardIt, class UnaryPredicate>
constexpr ForwardIt custom_partition(ForwardIt first, ForwardIt last,
                                     UnaryPredicate p)
{
    first = std::find_if_not(first, last, p);
    if (first == last) return first;

    for (ForwardIt i = std::next(first); i != last; ++i) {
        if (p(*i)) {
            std::iter_swap(i, first);
            ++first;
        }
    }
    return first;
}

The major difference between this implementation and our implementation was that the two pointers used in this implementation are both sliding from left to right whereas the two pointers used in our implementation are sliding from different directions. Therefore, this implementation will have at most $N$ swaps whereas our implementation will have at most $\frac{N}{2}$ swaps.

This implementation is somewhat more general than the one we implemented above in my opinion, because it follows the half open range convention in C++ STL and it did not use -- which might not have been implemented by the iterator of each STL container.