Inspiration
Alexander Stepanov and Paul McJones in the their book “Elements of Programming” (Chaper 11.1) describe a stable partition algorithm that appears to be more complex than necessary. Here I present an improvement.
Problem
Definition A partition of sequence with respect to a predicate P is a permutation of the sequence such that all elements satisfying the predicate appear before any element that does not or vice versa.
If x and y are two elements in the original sequence then a stable partition is one where P(x) = P(y) implies that x appears before y in the partitioned sequence if and only if x appears before y in the original sequence.
A semi stable partition is a partition that is stable only for P(x) = P(y)= false.
The following C++ function generates an in-place semi stable partition. Notice that using the C++ convention last points to one past the last element of the array.while first points to first element of the array.
template<class Iter,class Pred>
Iter stable_part(Iter first, Iter last, Pred P) {
Iter i = first;
Iter p = first;
// let [first',last') refer to the unmodified data
// Invariant
// [first,i) is semi-stable partitioned at p.
// In other words
// (1) x in [first,p) => !P(x)
// (2) x in [p,i) => P(x)
// (3) [first,i) is a permutation of
// [first', first' +(i-first))
// (4) x,y in [first,p) &
// x precedes y in [first,p) =>
// x precedes y in [first',first' +(i-first))
while(i!=last) {
if( P(*i))
++i;
else {
swap(*i,*p); ++i;++p;
}
}
return p;
}
Proof
Notice that the invariant is trivially established at the beginning of the loop. The if statement extends the sequence that is semi stable partitioned. Hence the loop invariant holds at the end of the if statement. Hence on termination of the loop p is a point of semi stable partition of the whole sequence.
