0

パーティション メソッドのループ本体が ArrayIndexOutOfBounds 例外をスローしないのはなぜですか?

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;
 }
4

1 に答える 1

0 
// m <= high (loop invariant)
while (m != high)  {
    // m < high, hence correct index
    a[m] ...

    m = m + 1;
    // m <= high (loop invariant)
}

マインドスワップは m を変更しません。k と m が入れ替わったと思ったかもしれませんが、おそらく a[k] と a[m] です。m はローカルの int 変数であるため、int は値によって渡されます。

m と k が入れ替わったとしても: m <= high

ループ不変条件 k <= m はヘルトです:

// k <= m
if (...) {
    swap(a, k, m);
    // m <= old m // if call-by-reference

    k = k + 1;
    // k - 1 <= m if call-by-value
}
m = m + 1;
// k <= m again; if call-by-value
于 2012-12-01T23:13:20.247 に答える