Implementing Quicksort

Question

i am trying to implement quicksort but i am not getting correct results. Here is my code:

public static void quickSort(Comparable[] a, int start, int stop) {
    if (start < stop) {
        int pivot = partition(a, start ,stop);
        System.out.print("Pivot: "+a[pivot]+" Array: ");
        printArray(a);
        quickSort(a,start,pivot-1);
        quickSort(a,pivot+1, stop);
    }       
}

public static int partition(Comparable[] a, int start, int stop) {
    Comparable pivot = a[stop];
    int i = start;
    int j = stop-1;


     while (i < j) {
            while( (isLess(a[i], pivot)|| isEqual(a[i], pivot)))
                i++;
            while((isGreater(a[j], pivot)|| isEqual(a[j], pivot)))
                j--;
            if(i < j)
                swap(a, i,j);
        } 

    swap(a,i, stop);

    return i;

}

For input: {51,17,82,10,97,6,23,45,6,73}, i am getting result: 6 6 10 17 23 45 51 73 97 82 For input: {12,9,4,99,120,1,3,10}, i am getting an index out of bounds error. Would appreciate some help in where i am going wrong.

Answer 1

I recommend you Algorithms: Design and Analysis, very good internet course from Stanford. After this course you will write such codes more easily. It is a bit enhanced version, pivot is chosen as a median of three. Note that you don't have to write your own printArray() function. In Java you can do it with System.out.println(Arrays.toString(numbers)). Also you can observe how to call quickSort() in more elegant way, with only one argument, using method overloading.

public class QuickSort
{

public static void main(String[] args)
{
    int numbers[] =
    { 51, 17, 82, 10, 97, 6, 23, 45, 6, 73 };
    quickSort(numbers);
    System.out.println(Arrays.toString(numbers));
}

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

private static void quickSort(int[] array, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int pivot = choosePivot(array, left, right);
    pivot = partition(array, pivot, left, right);
    quickSort(array, left, pivot - 1);
    quickSort(array, pivot + 1, right);
}

private static int partition(int[] array, int pivot, int left, int right)
{
    swap(array, pivot, left);
    pivot = left;
    int i = left + 1;
    for (int j = left + 1; j <= right; j++)
    {
        if (array[j] < array[pivot])
        {
            swap(array, j, i);
            i++;
        }
    }
    swap(array, pivot, i - 1);
    return i - 1;
}

private static void swap(int[] array, int j, int i)
{
    int temp = array[j];
    array[j] = array[i];
    array[i] = temp;
}

private static int choosePivot(int[] array, int left, int right)
{
    return medianOfThree(array, left, (left + right) / 2, right);
    // return right;
}

private static int medianOfThree(int[] array, int aIndex, int bIndex, int cIndex)
{
    int a = array[aIndex];
    int b = array[bIndex];
    int c = array[cIndex];
    int largeIndex, smallIndex;
    if (a > b)
    {
        largeIndex = aIndex;
        smallIndex = bIndex;
    }
    else
    {
        largeIndex = bIndex;
        smallIndex = aIndex;
    }
    if (c > array[largeIndex])
    {
        return largeIndex;
    }
    else
    {
        if (c < array[smallIndex])
        {
            return smallIndex;
        }
        else
        {
            return cIndex;
        }
    }
}

}

Answer 2

Your two problems are unrelated.

The problem with {51,17,82,10,97,6,23,45,6,73} is — what happens when stop == start + 1? Then i == start == stop - 1 == j, so you never enter the while-loop, so you unconditionally swap(a, i, stop) — even if a[i] was already less than a[stop].

The problem with {12,9,4,99,120,1,3,10} is seemingly that you didn't read the stacktrace. ;-)   Assuming you have a decent Java compiler and JVM, it should have given you the exact line-number and problematic index, so you would have seen that the problem is in this line:

            while((isGreater(a[j], pivot)|| isEqual(a[j], pivot)))

once j gets to -1. (This will happen if pivot is the very least value in the range of interest.) You just need to add a check for that:

            while(j > start && (isGreater(a[j], pivot)|| isEqual(a[j], pivot)))

(and, for that matter, for the corresponding case of i:

            while(i < stop && (isLess(a[i], pivot)|| isEqual(a[i], pivot)))

)

. . . and you need to learn how to debug your code. :-)