reneargento/algorithms-sedgewick-wayne

Ex 2.3.1: omit one extra line

Forest-Lee opened this issue · 1 comments

private static int partition(Comparable[] a, int lo, int hi) {
    int i = lo, j = hi + 1;
    Comparable v = a[lo];
    while (true) {
        while (less(a[++i], v)) {
            if (i == hi) break;
        }
        while (less(v, a[--j])) {
            if (j == lo) break;
        }
        if (i >= j) break;
        exch(a, i, j);
    }
    exch(a, lo, j);
    return j; 
}

According to partition method, I think there should be one extra line for the final exch(a, lo, j) in this exercise.
Therefore, the answer should be as follows.

                                a[]                 
        i   j   0  1  2  3  4  5  6  7  8  9  10  11     
init	0   12  E  A  S  Y  Q  U  E  S  T  I   O   N    
scan	2   6   E  A  S  Y  Q  U  E  S  T  I   O   N    
exch	2   6   E  A  E  Y  Q  U  S  S  T  I   O   N 
scan	3   2   E  A  E  Y  Q  U  S  S  T  I   O   N      
exch    3   2   E  A  E  Y  Q  U  S  S  T  I   O   N                          
res         2   E  A  E  Y  Q  U  S  S  T  I   O   N

Having one extra line with the result makes sense.
I updated the exercise here: 23df276
Thanks!