Recursive QuickSort in java not working

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

ajb · Accepted Answer · 2016-11-24 19:45:48Z

2

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.

answered Nov 24, 2016 at 19:45

ajb

31.8k4 gold badges63 silver badges86 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Linxy Over a year ago

Thanks a lot, the for loop was iterating one time less than it should and it was pure luck that it worked on some occasions.

Collectives™ on Stack Overflow

Recursive QuickSort in java not working

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related