Quicksort not completely sorting provided array

Question

My Quicksort seems to stop before completely sorting the array, and I've stared myself blind on the code.

I wrote the algorithm according to the related chapters in Java Software Structures - Designing and Using Data Structures (3rd Edition)

Quick Sort:

private static <T extends Comparable<T>> void quickSort(T[] array,int min, int max){

    int pIndex;

    if (max-min > 0) {

        pIndex = partition(array, min, max);

        quickSort(array, min, pIndex-1);

        quickSort(array, pIndex+1, max);

    }
}

Partition:

private static <T extends Comparable<T>> int partition(T[] array, int min, int max) {

    int left, right;
    T pivot, temp;
    int middle = (min+max)/2;

    left  = min;
    right = max;
    pivot = array[middle];

    while (left < right) {

        while (array[left].compareTo(pivot) <= 0 && left < right)
        left++; 

        while (array[right].compareTo(pivot) > 0)
        right--;

        if (left<right) {
            temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }

    }

    temp = array[min];
    array[min] = array[right];
    array[right] = temp;

    return right;
}

The input:
An int[10] array containing the values 0 through 9, shuffled.
The quicksort-function is thus called like: quicksort(nums, 0, nums.length-1)

The output (example):

As you can see, the end product seems to be somewhat on the way to a good end-product, but it's stopping prematurely somewhere.

Update:
None of the answers provided so far (the deleted ones included) worked. If nobody is able to spot the bug, would anyone kindly redirect me to a good source for generic algorithms in Java?

I even shamefully attempted to do a pure copypaste of the Quicksort algorithm from the book mentioned above, and while it compiled and ran, it resulted in the same, "almost-correct" output as above. I then questioned whether or not it may be my input data, but nope. It is simply an Integer-array of integers, no duplicates. It's a valid candidate to my understanding.

Have you considered dumping out the entire contents of the array to the console, as well as passing around a "depth meter" so you can determine at what depth in the recursion the error occurred? A simple integer would serve as a depth meter. For a list of size 10 or less, I imagine that this would not be overwhelming to look at. — Rainbolt
– Rainbolt, Commented Feb 27, 2014 at 22:55
I would suggest constructing a test array with around 10 values, and then sort it by hand first using QuickSort (as you understand it to be) so you know what your algorithm should do, and then step through using a debugger (print out the array when needed) and see when the behavior changes from what you expected. At that point start looking for the bug. Repeat until you get the expected result. — Thorbjørn Ravn Andersen
– Thorbjørn Ravn Andersen, Commented Feb 27, 2014 at 22:59
@ThorbjørnRavnAndersen - Better than my suggestion of finding a Knuth text and going from there :) — KevinDTimm
– KevinDTimm, Commented Feb 27, 2014 at 23:00
Also, do not feel bad about this. QuickSort is notoriously hard to get right the first time. — Thorbjørn Ravn Andersen
– Thorbjørn Ravn Andersen, Commented Feb 27, 2014 at 23:00
@KevinDTimm as long as you serve as the mentor all the way, I think your suggestion is clearly superior. — Thorbjørn Ravn Andersen
– Thorbjørn Ravn Andersen, Commented Feb 27, 2014 at 23:00

FDinoff · Accepted Answer · 2014-02-28 18:09:02Z

1

I was able to get quick sort to sort some test arrays with the following partition function.

private static <T extends Comparable<T>> int partition(T[] array, int min, int max) {

    int left, right;
    T pivot, temp;
    int middle = (min+max)/2;

    left  = min;
    right = max ;
    pivot = array[middle];

    while (left < right) {

        while (array[left].compareTo(pivot) < 0 && left < right)
            left++; 

        while (array[right].compareTo(pivot) > 0)
            right--;

        if (left<right) {
            temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }
    }
    return right;
}

All I changed was the first compareTo comparison to be less than instead of less than or equal to. This allows the pivot to move in the array. This however does mean that the array CANNOT contain duplicates. I also removed the last swap as I couldn't tell what it was doing.

The problems stem from how you deal with the pivot. It doesn't actually partition the array properly.

This also works and allows duplicates.

private static <T extends Comparable<T>> int partition(T[] array, int min, int max) {
    int left, right;
    T pivot, temp;
    int middle = (min+max)/2;

    left  = min + 1;
    right = max ;
    pivot = array[middle];

    // move partition element to min index
    temp = array[min];
    array[min] = array[middle];
    array[middle] = temp;

    while (left < right) {

        while (array[left].compareTo(pivot) <= 0 && left < right)
            left++; 

        while (array[right].compareTo(pivot) > 0)
            right--;

        if (left<right) {
            temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }

    }

    // move partition element to partition index
    temp = array[min];
    array[min] = array[right];
    array[right] = temp;
    return right;
}

I looked up a copy of the book. The comment tells you what the last swap was trying to do. Which makes my fix of adding a swap at the begging to move the partition element to the min index the correct fix.

edited Feb 28, 2014 at 18:09

answered Feb 28, 2014 at 2:46

FDinoff

31.6k5 gold badges79 silver badges99 bronze badges

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

4 Comments

Thorbjørn Ravn Andersen Over a year ago

If the array cannot contain duplicates now, is it the right solution then?

krystah Over a year ago

It. Is. Sorting. For now, I don't care about duplicates, I'm gonna delve deeper into this now and make improvements. At least now something is running! Thanks for the advice, all of you =)

FDinoff Over a year ago

@ThorbjørnRavnAndersen I looked up a copy of the book to figure out what that last swap was doing. It was moving the pivot into the middle of the array. However the original code didn't move the pivot originally so it was swapping to random elements. I fixed the solution so that it can contain duplicates now.

FDinoff Over a year ago

@krystah updated to work with duplicates. (The comment from the book helped in understanding what that last swap was doing).

user207421 · Accepted Answer · 2014-02-28 00:07:03Z

0

while (array[left].compareTo(pivot) <= 0 && left < right)
    left++; 

while (array[right].compareTo(pivot) > 0)
    right--;

These loops are usually written:

while (array[left++].compareTo(pivot) <= 0 && left < right)
    ; 

while (array[right--].compareTo(pivot) > 0)
    ;

The idea is to stop at the first element that doesn't belong in this partition.

answered Feb 28, 2014 at 0:07

user207421

312k45 gold badges324 silver badges493 bronze badges

Collectives™ on Stack Overflow

Quicksort not completely sorting provided array

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related