QUICKSORT : how to resolve java.lang.StackOverflowError?

Question

I am writing a quicksort program to run on an input size of 100000. I have tried running it at a size of 500 and it works fine but with million inputs, the program breaks with the following error code

"java.lang.StackOverflowError"

Can someone please help me how to resolve this problem? I am pretty sure that I am not caught in an infinite recursion. There is a base case which should cause the recursive method to return.

public class count_comparisons {

    public static int count_comp =0;
    public static int partitioning(int[] A, int lo, int hi) {

        int pivot = A[lo];

        int i=lo+1;
        int j=lo+1;
        int k=lo;

        for ( j=lo+1;j<=hi;j++) {            
            if (A[j] < pivot) {
                swap(A,i,j);
                i++;
            }
        }
        swap(A,i-1,lo);        
        return i-1;
    }

    public static int quicksort(int[] A, int lo, int hi) {
        if (lo>=hi) return 0;
        int pivot = partitioning(A,lo,hi);

        //StdOut.println("Pivot index is "+ pivot +" and entry at pivot is " + A[pivot]);

        StdOut.println("Lo is "+ lo +" and Hi is " + hi);
        int h = quicksort(A,lo,pivot-1);
        int m = quicksort(A,pivot+1,hi);
        //StdOut.println("First half count is "+h);
        //StdOut.println("Second half count is "+m);
        count_comp = count_comp + h + m;
        return (hi-lo);
    }

    public static void quicksort(int[] A,int N) {  
        int k = quicksort(A,0,N-1);
        count_comp = count_comp + k;
        //StdOut.println(" First count is "+k);
    }

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

    public static void main(String[] args) {
        In in = new In("input_file.txt"); 
        int N=569;
        int[] A = new int[569];
        int i=0;
        while (!in.isEmpty()) {
            A[i++] = in.readInt();
        }
        count_comparisons.quicksort(A,N);

        for( int h=0;h<N;h++) {}
            //StdOut.print(A[h]);
        StdOut.println();
        StdOut.println(count_comparisons.count_comp);

    }
}

there are 2 solutions - rewrite program to not use recursion (better) or increase -Xss parameter (easier) — JIV, Jul 08 '13 at 14:57
you could increase the stack size, or you could manually manage the stack in a more iterative solution so that you would be doing the work on the heap instead of the call stack — mistahenry, Jul 08 '13 at 14:58
Here you have some info how to increase JVM stack size: http://stackoverflow.com/questions/3700459/how-to-increase-to-java-stack-size — Fuv, Jul 08 '13 at 15:03
@JIV Even [Java's implementation of `quicksort`](http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/Arrays.java#904) is recursive. — Marko Topolnik, Jul 08 '13 at 15:05
Given an input size of 100000, i'd estimate an maximum recursion depth of say 20, unless you feed quicksort with ill-fated data. Why dont you give us the output of your printlns (should give an idea if your algorithm works as expected) and some of the stacktrace? — Gyro Gearless, Jul 08 '13 at 15:23

score 2 · Answer 1 · answered Jul 08 '13 at 15:00

Recursion does not need to be infinite in order to cause stack overflow: all it needs it to be just long enough to overflow the stack.

Quicksort may be very slow: under some particularly unfortunate circumstances, it may take up to n-1 invocations, for the worst-case performance of O(n^2).

You have two choices - rewrite the code without recursion by using an explicit stack data structure, or by increasing the size of stack that JVM allocates to your program's threads.

@Alnitak the implementation of `Collections#sort` is a merge sort, not a quick sort =\ — Luiggi Mendoza, Jul 08 '13 at 15:02

score 0 · Answer 2 · answered Jul 08 '13 at 15:03

0

There is a trick with tail-recursion-elimination and recursing only into the smaller subset, which limits the recursion depth.

answered Jul 08 '13 at 15:03

Markus Kull

1,471
13
16

QUICKSORT : how to resolve java.lang.StackOverflowError?

2 Answers2