bug in java quicksort algorithm implementation

Question

somehow the last element of my input does not get sorted with the list i am feeding to the quicksort method
for example

input : 5,7,3,2,7,8,9,0,3,1,2,3
result: 0 1 2 2 3 3 5 7 7 8 9 3

input: 5,4,2,12,9,4
result: 2 4 5 9 12 4

any ideas where i am going wrong?

public class QuickSort2 {

    private static void quickSort(int[] list) {
        quickSort(list, 0, list.length - 1);
    }

    private static void quickSort(int[] list, int p, int q) {
        if (p < q) {
            int pivotIndex = partition(list, p, q);
            quickSort(list, p, pivotIndex - 1);
            quickSort(list, pivotIndex + 1, q);
        }
    }

    private static int partition(int[] list, int p, int q) {
        int x = list[p];
        int i = p;
        int temp, temp2;
        for (int j = p + 1; j < list.length - 1; j++) {
            if (list[j] < x) {
                i = i + 1;
                // exchange list[i] with list[j]
                temp = list[i];
                list[i] = list[j];
                list[j] = temp;
            }
        }
        // exchange list[p] with list[i]
        temp2 = list[p];
        list[p] = list[i];
        list[i] = temp2;
        return i;
    }
}

edit

public class QuickSort2 {

    private static void quickSort(int[] list) {
        quickSort(list, 0, list.length - 1);
    }

    private static void quickSort(int[] list, int p, int q) {
        if (p < q) {
            int pivotIndex = partition(list, p, q);
            quickSort(list, p, pivotIndex - 1);
            quickSort(list, pivotIndex + 1, q);
        }
    }

    private static int partition(int[] list, int p, int q) {
        int x = list[p];
        int i = p;
        int temp, temp2;
        for (int j = p + 1; j <= q; j++) {
            if (list[j] < x) {
                i = i + 1;
                // exchange list[i] with list[j]
                temp = list[i];
                list[i] = list[j];
                list[j] = temp;
            }
        }
        // exchange list[p] with list[i]
        temp2 = list[p];
        list[p] = list[i];
        list[i] = temp2;
        return i;
    }
}

icza · Accepted Answer · 2014-09-12 08:24:44Z

4

Your for loop "skips" the last element:

for (int j = p + 1; j < list.length - 1; j++)

Modify it like this:

for (int j = p + 1; j < list.length; j++)

Btw it should be not be list.length because that way you're doing unnecessary work. You're supposed to work on the [p..q] (both inclusive) range and not on the whole array, so this is enough:

for (int j = p + 1; j <= q; j++)

You're implementation (even though it works) looks atypical. Take a look at Quicksort.

edited Sep 12, 2014 at 8:24

answered Sep 12, 2014 at 7:45

icza

423k78 gold badges1k silver badges905 bronze badges

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

1 Comment

tmax Over a year ago

thank you that pretty much fixes what i was looking for

Collectives™ on Stack Overflow

bug in java quicksort algorithm implementation

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