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

Filed under:
|

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

Related posts about java

Related posts about quicksort