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