Quick Sort stackoverflow error for large arrays

Question

So I was assigned to implement a quick sort algorithm and compare the running times for arrays with size 500, 3500, and 80000. The arrays are populated with random numbers:

(int)Math.random()*1000000

My quicksort algorithm works for the arrays with size 500 and 3500, but I always get a stackoverflow error when I try to sort the third array with size 80000. My other sorting algorithms handle these arrays just fine.

My quick sort method:

public static void quickSort(int[] a, int p, int r)
{
    if(p<r)
    {
        int q=partition(a,p,r);
        quickSort(a,p,q);
        quickSort(a,q+1,r);
    }
}

My partition method:

private static int partition(int[] a, int p, int r) {

    int x = a[p];
    int i = p;
    int j = r;

    while (true) {
        do {
            i++;
        } while (i < r && a[i] < x);
        do {
            j--;
        } while (j > p && a[j] > x);

        if (i < j) {
            int tmp = a[i];
            a[i++] = a[j];
            a[j--] = tmp;
        } else {
            return j;
        }
    }
}

I read that I could simply change my stack size in the VM options (not sure how to do that) but that is just ignoring the problem in my algorithm. What's causing the error? Thanks!

My driver class:

public class Driver {

    public static void main(String[] args) {

        int[] array1 = new int[500];
        int[] array2 = new int[3500];
        int[] array3 = new int[80000];

        for(int i=0; i<array1.length; i++) {
            array1[i]=(int)(Math.random()*100000);
        }

        for(int i=0; i<array2.length; i++) {
            array2[i]=(int)(Math.random()*100000);
        }

        for(int i=0; i<array3.length; i++) {
            array3[i]=(int)(Math.random()*100000);
        }

        //~~~~~~~~~~~INSERTION~~~~~~~~~~~~~~~//

        System.out.println("INSERTION SORT:\n_______________");
        System.out.println("500 Elements: "+SortTimes.runTime(SortTimes.INSERTION,array1)+" ms");
        System.out.println("3500 Elements: "+SortTimes.runTime(SortTimes.INSERTION,array2)+" ms");
        System.out.println("80000 Elements: "+SortTimes.runTime(SortTimes.INSERTION,array3)+" ms");

        //~~~~~~~~~~~BUBBLE~~~~~~~~~~~~~~~//

        System.out.println("\n\nBUBBLE SORT:\n_______________");
        System.out.println("500 Elements: "+SortTimes.runTime(SortTimes.BUBBLE,array1)+" ms");
        System.out.println("3500 Elements: "+SortTimes.runTime(SortTimes.BUBBLE,array2)+" ms");
        System.out.println("80000 Elements: "+SortTimes.runTime(SortTimes.BUBBLE,array3)+" ms");

        //~~~~~~~~~~~MERGE~~~~~~~~~~~~~~~//

        System.out.println("\n\nMERGE SORT:\n_______________");
        System.out.println("500 Elements: "+SortTimes.runTime(SortTimes.MERGE,array1)+" ms");
        System.out.println("3500 Elements: "+SortTimes.runTime(SortTimes.MERGE,array2)+" ms");
        System.out.println("80000 Elements: "+SortTimes.runTime(SortTimes.MERGE,array3)+" ms");

        //~~~~~~~~~~~QUICK~~~~~~~~~~~~~~~//

        System.out.println("\n\nQUICK SORT:\n_______________");
        System.out.println("500 Elements: "+SortTimes.runTime(SortTimes.QUICK,array1)+" ms");
        System.out.println("3500 Elements: "+SortTimes.runTime(SortTimes.QUICK,array2)+" ms");
        System.out.println("80000 Elements: "+SortTimes.runTime(SortTimes.QUICK,array3)+" ms");
    }
}

Here is my SortTimes class:

public class SortTimes {

    public final static int MERGE = 1;
    public final static int QUICK = 2;
    public final static int BUBBLE = 3;
    public final static int INSERTION = 4;

    public static double runTime(int sortMethod, int[] array) {

        double startTime;
        double endTime;

        switch(sortMethod) {
            case MERGE:
                startTime = System.currentTimeMillis();
                lab12.mergeSort(array);
                endTime = System.currentTimeMillis();
                break;

            case QUICK:
                startTime = System.currentTimeMillis();
                lab12.quickSort(array, 0, array.length-1);
                endTime = System.currentTimeMillis();
                break;

            case BUBBLE:
                startTime = System.currentTimeMillis();
                lab12.bubbleSort(array);
                endTime = System.currentTimeMillis();
                break;

            case INSERTION:
                startTime = System.currentTimeMillis();
                lab12.insertionSort(array);
                endTime = System.currentTimeMillis();
                break;

            default:
                startTime = -1;
                endTime = 0;
                break;
        }

        return endTime-startTime;
    }
}

Answer 1

Here is your quicksort:

public static void quickSort(int[] a, int p, int r)
{
    if(p<r)
    {
        int q=partition(a,p,r);
        quickSort(a,p,q);
        quickSort(a,q+1,r);
    }
}

It works, but in the worst case it uses O(r-p) stack space. That is too much for real implementations. The fix is easy, though -- you recurse on the smaller partition, and then loop for the larger partition. Recursing on the smaller partition means you use only O(log(r-p)) stack space no matter what:

public static void quickSort(int[] a, int p, int r)
{
    while(p<r)
    {
        int q=partition(a,p,r);
        if (q-p <= r-(q+1))
        {
            quickSort(a,p,q);
            p=q+1;
        }
        else
        {
            quickSort(a,q+1,r);
            r=q;
        }
    }
}

EDIT: so, this is the way that real quicksort implementations ensure that there are no stack overflows in the worst case...

BUT the worst case never happens when you initialize an array with random numbers.

You said that you initialized the array with (int)Math.random()*1000000. Check the precedence tables! The cast happens before the multiply, so this is always 0, which is why you are getting worst case behaviour. You want (int)(Math.random()*1000000).

EDIT: Your partition function is also broken. It will always leave a[p] at position p, even if it is the largest element in the array

Answer 2

You're reporting a stack overflow with an 80 thousand element array. Your code sorts an 80 million element array on my laptop with no problems in about 10 seconds. I don't see any stack overflow errors...

If you have a random input, you should expect the maximum recursion depth to be somewhere in the ballpark of log₂(n), which is less than 30 for n=80,000,000. The quicksort wikipedia article has a more detailed analysis. Basically, unless you hit a really pathological case (where all your pivots are terrible), you shouldn't expect to see so much recursion that the stack overflows.

However, I did have to fix a couple of logic errors in the code in order to actually get a valid sort (I wasn't getting a fully-sorted result).

---

Fix your random number generation

(int)Math.random()*1000000 will always return zero. You need to add another set of parentheses to truncate after the multiplication: (int)(Math.random()*1000000).

Fix your partition logic

Your partition method almost matches the logic for the Hoare partitioning scheme. However, you seem to have a few off-by-one errors. If you compare your code with the code from wikipedia, you will see a few differences.

1. You set i=p and j=r, but it should be i=p-1 and j=r+1.
2. You should remove the increment and decrement in your swapping logic, so a[i++] should just be a[i], and a[j--] should just be a[j].

---

Here's the code I used to test this:

public class QSort {

    private static int partition(int[] a, int p, int r) {

        int x = a[p];
        int i = p-1;
        int j = r+1;

        while (true) {
            while (++i < r && a[i] < x);
            while (--j > p && a[j] > x);

            if (i < j) {
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            } else {
                return j;
            }
        }
    }

    public static void quickSort(int[] a, int p, int r) {
        if(p<r) {
            int q=partition(a,p,r);
            quickSort(a,p,q);
            quickSort(a,q+1,r);
        }
    }

    public static void main(String args[]) {
        int n = Integer.valueOf(args[0]);
        int[] xs = new int[n];
        for (int i=0; i<n; i++) {
            xs[i] = (int)(Math.random()*1000000);
        }
        quickSort(xs, 0, xs.length-1);
        for (int i=0; i<n-1; i++) {
            if (xs[i] > xs[i+1]) {
                System.out.println("ERROR");
                System.exit(-1);
            }
        }
        System.out.println("SORTED");
    }

}