Semi-Stable Partition

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.

Advertisements

About The Sunday Programmer

Joe is an experienced C++/C# developer on Windows. Currently looking out for an opening in C/C++ on Windows or Linux.
This entry was posted in Algorithm, C++. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s