// partition.C
#include "partition.h"
#include "swap.h"

int partition(int vec[],
               int loBound, int hiBound) 
{
  // ASSERT: there are 3 or more items
  int pivot = vec[(loBound+hiBound)/2];
  vec[(loBound+hiBound)/2] = vec[loBound];
  vec[loBound] = pivot;
  int loSwap = loBound + 1;
  int hiSwap = hiBound;
  do {
    while (loSwap <= hiSwap
	   && vec[loSwap] <= pivot) {
      loSwap++;
    }
    // ASSERT: loSwap <= hiSwap+1
    // && all vec[loBound+1..loSwap-1]
    // are <= pivot && (loSwap < hiSwap)
    // --> vec[lowSwap] > pivot

    while (vec[hiSwap] > pivot) {
      hiSwap--;
    }
    // ASSERT: hiSwap >= loSwap-1
    // &&  All vec[hiSwap+1..hiBound]
    // are > pivot && vec[hiSwap] <= pivot

    if (loSwap < hiSwap) {
      swap(vec[loSwap], vec[hiSwap]);
    }
    // INV: vec[loBound..loSwap-1] <=pivot
    // && vec[hiSwap+1..hiBound] > pivot
    // && (loSwap < hiSwap) -->
    //  vec[loSwap] <= pivot < vec[hiSwap]
    // && (loSwap >= hiSwap) -->
    //  vec[hiSwap] <= pivot
    // && loBound <= loSwap <= hiSwap+1
    // && hiSwap+1 <= hiBound+1
  } while (loSwap < hiSwap);
  vec[loBound] = vec[hiSwap];
  vec[hiSwap] = pivot;
  return hiSwap;
}