Linxy - 5 months ago 34

Java Question

I am trying to implement a quicksort in java which has the last element of the array as a pivot. However, it does not seem to be working even though on paper it should..

This is the output:

`before sort: 5 2 3 1 4`

after sort: 3 2 4 5 1

The expected output would be 1,2,3,4,5 but that doesn't seem to be happening.

`public static void main(String[] args) {`

int A[] = {5,2,3,1,0};

ArrayUtils.printArray("before sort", A);

quick_sort(A, 0, A.length-1);

ArrayUtils.printArray("after sort", A);

}

public static void quick_sort(int[] A, int p, int r) {

if (p < r) {

int q = partition(A, p, r);

quick_sort(A, p, q-1);

quick_sort(A, q+1, r);

}

}

I have tracked the problem down to be in partition with the debugger, but I cannot seem to find where it is. It seems for loop sometimes will produce a wrong i, but sometimes it works correctly.. I am not sure, that is why i am asking.

`public static int partition(int A[], int p, int r) {`

int x = A[r];

int i = p-1;

for(int j = p; j < r-1; j++) {

if (A[j] <= x) {

i = i + 1;

int temp = A[j];

A[j] = A[i];

A[i] = temp;

}

}

int temp = A[r];

A[r] = A[i + 1];

A[i + 1] = temp;

return i + 1;

}

where printArray() is

`public static void printArray(String name, int[] array) {`

if (array.length >= 10) {

System.out.print(name + ": \n");

} else {

System.out.print(name + ": ");

}

for(int i = 0; i < array.length; i++) {

if (i % 10 == 0 && i > 0) {

System.out.print("\n");

}

System.out.print(array[i] + " ");

}

System.out.println("\n");

}

Answer

It looks like your partition algorithm looks is based on the Lomuto partition scheme in Wikipedia. However, in Wikipedia, the pseudo-code says `for j := lo to hi - 1`

, which is based on Pascal syntax. In Pascal-like languages, that means that the last value of `j`

is `hi - 1`

. In C-like languages such as Java, we usually make the upper bound the value *after* the last value the index will have, instead of the last value. That means that in your code, `j`

will never actually have the value `hi - 1`

. Fixing the `for`

loop to make sure `j`

does take the value `r-1`

makes things work, with your example.