public class partition {
static int partition(int[] a, int first, int last) {
// pre condition :
assert(a != null);
assert(0 <= full && first < last && last < a.length);
int x = a[first];
int h = first;
for (int k = first +1; k <= last; k++) {
/**
* Invariant: the element from position first+1 to k are
* smaller than x, and the elements from h+1 to k-1 are
* bigger than or equal to x.
*/
elementsComparisions++;
if(a[k] <x) {
h = h +1;
swap(a,h,k);
}
}
swap(a, first, h);
/**
* Post-condition:
* The elements of a from first to h-1 are smaller than a[h] and
* the elements of a from h+1 to last are bigger than or equal to a[h]
*/
return h;
}
}