Partition loop understanding
Posted
by
user1795732
on Stack Overflow
See other posts from Stack Overflow
or by user1795732
Published on 2012-12-01T22:55:29Z
Indexed on
2012/12/01
23:03 UTC
Read the original article
Hit count: 161
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;
}
© Stack Overflow or respective owner