xor - 1 month ago 15
Java Question

# Quicksort Counter Example

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`
method along with some other stuff:

``````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`
method.
`0`
, as the index of the pivot, makes sense in terms of the definition, i.e.
`everything left of the pivot is smaller and everything right of the pivot is larger`
, but clearly runs into a problem in
`sort`
namely:

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

where you have the right pointer being negative (
`j-1 = 0-1 = -1`
). My question again being is there a modification to the above method(s) that will maintain the definition (
`everything left of the pivot is smaller and everything right of the pivot is larger`
) and not run into the problem in
`sort`
.

``````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.