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
1 |
|
1 | $ g++ partition.cpp -o partition --std=c++14 |
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.
1 | template <class ForwardIt, class UnaryPredicate> |
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.
Partition Algorithm