Linxy Linxy - 9 days ago 5
Java Question

Recursive QuickSort in java not working

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");
}

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

Comments