Ch20's partition function may access invalid memory

[GoogleCodeExporter]

In Ch20, 20.2.1, Sorting concurrently,  partition's implementation might access 
the invalid memory.

1   int partition(int a[], int i, int j) {
2     int v, k, t;
3     j++;
4     k = i;
5    v = a[k];
6    while (i < j) {
7        i++; while (a[i] < v && i < j) i++; 
8        j--; while (a[j] > v) j--;
9        if (i < j) { t = a[i]; a[i] = a[j]; a[j] = t; }
10  }
11  t = a[k]; a[k] = a[j]; a[j] = t;
12  return j;
13 }

For example:

int a[5] = {5,4,3,2,1};
partition(a,0,4);

line 3 increments j to 5,  line 7's a[i] < v will access a[5], which is out of 
the upper boundary of array.

Maybe, line 7 should be changed as 
i++; while (i < j && a[i] < v) i++; 

Original issue reported on code.google.com by ligong...@gmail.com on 9 Jul 2012 at 2:45

[GoogleCodeExporter]

Looks good to me. I'll make the suggested change next time I edit CII code.

Original comment by drhan...@gmail.com on 23 Jul 2012 at 4:49

• Changed state: Accepted

[GoogleCodeExporter]

Original comment by drhan...@gmail.com on 23 Jul 2012 at 4:51