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.

$ 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.

template <classForwardIt, classUnaryPredicate> 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.