xor - 3 months ago 35

Java Question

Firstly (as the question title implies) I'm not looking for why the bellow partitioning method doesn't work, rather a modification to it so that it will work for the following input:

`int[] a = {1,2,8,4,5,7};`

Here's the

`partition`

`static int[] swap (int[] a,int i,int j){`

int t = a[i];

a[i] = a[j];

a[j] = t;

return a;

}

static int partition (int[] a,int l,int r){

int i = l;

int j = r;

int v = a[l];

while (true) {

while (a[i] < v) {

if (i == r) break;

i++;

}

while (a[j] > v) {

if (j == l) break;

j--;

}

if (i >= j) break;

a = swap(a,i,j);

}

a = swap(a, l, j);

return j;

}

void sort(int[] a,int l,int r){

int j = partition(a, l, r);

sort(a, l, j-1);

sort(a, j+1, r);

}

public static void main(String[] args) {

int[] a = {1,2,8,4,5,7};

System.out.println(partition(a,0,5));

}

Output:

`0`

The output is the index of the pivot returned from the

`partition`

`0`

`everything left of the pivot is smaller and everything right of the pivot is larger`

`sort`

`sort(a, l, j-1);`

where you have the right pointer being negative (

`j-1 = 0-1 = -1`

`everything left of the pivot is smaller and everything right of the pivot is larger`

`sort`

Answer

The missing part is the line

```
if ( l >= r ) return;
```

in the beginning of the `sort`

method. This is actually the recursion stop step so it is necessary to have it anyway to prevent endless recursion. But besides that, it also solves your problem, because if you call `sort(0,-1)`

then -1 is less than 0, so it prevents further processing of that index.