Quick Sort stackoverflow error for large arrays

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

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

}

Since this program is recursive and java is not memory efficient in recursions that goes a bit deep, try increasing the amount of memory allocated for your program by the IDE.

Since you're using Intellij, try to increase memory as follows.

More Info : https://www.jetbrains.com/idea/help/run-debug-configuration-application.html

The recursive QuickSort algorithm on large arrays causes StackOverflow error.

Try the non-recursive one from this link. Following Java code is converted from original c code, hope it helps.

static final int MAX_LEVELS = 1000;
public static boolean quickSort(int[] arr, int elements) {
    int i=0,L,R,pivot;
    int[] beg = new int[MAX_LEVELS], end = new int[MAX_LEVELS];
    beg[0]=0;
    end[0]=elements;
    while(i>=0) {
        L=beg[i];
        R=end[i]-1;
        if(L<R) {
            pivot=arr[L]; if(i==MAX_LEVELS-1) return false;
            while(L<R) {
                while(arr[R]>=pivot&&L<R) R--; if(L<R) arr[L++]=arr[R];
                while(arr[L]<=pivot&&L<R) L++; if(L<R) arr[R--]=arr[L];
            }
            arr[L]=pivot;
            beg[i+1]=L+1;
            end[i+1]=end[i];
            end[i++]=L;
        } else {
            i--;
        }
    }
    return true;
}
// an example
public static void main(String[] args) {
    // construct the integer array
    int[] arr = new int[80000];
    for(int i=0;i<arr.length;i++) {
        arr[i]=(int)Math.random()*100000;
    }

    // sort the array
    quickSort(arr, arr.length);
}

It's time-saving and stackoverflow-immune.

Is your arrays inputed sorted? Did you pass a sorted array to quick sort?

public class quickSortTest {
public static void main(String[] args) {
    int max = 800000;
    int[] array = new int[max];
    for (int i = 0; i < max; ++i) {
        array[i] = (int) Math.random() * 1000000;
    }
    long start = System.currentTimeMillis();
    quickSort(array, 0, max - 1);
    System.out.println("time:"+(System.currentTimeMillis()-start));
    System.out.println(testSortResult(array));
}

public static boolean testSortResult(int[] array){
    for(int i=1;i<array.length;++i){
        if(array[i]<array[i-1]){
            return false;
        }
    }
    return true;
}

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

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 test your code , it's ok even when array lenght is 800000.