Partition loop understanding
- by user1795732
Why the loop body of the partition method never throws an ArrayIndexOutOfBounds Exception?
public static int partition( int[] a, low, high ) {
int k = low, m = low;
/* loop invariant:
* low <= k <= m <= high and
* all elements in a[low..k-1] are RED (i.e., < pivot) and
* all elements in a[k..m-1] are BLUE (i.e., >= pivot)
*/
while (m != high) {
if (a[m] >= pivot) // a[m] is BLUE
{ }
else { // a[m] is RED
swap(a,k,m);
k = k+1;
}
m = m+1;
}
return k;
}
