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

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.

Comments