Got stackoverflowerror when using quickSort, can I increase the stack and the heap?

Question

Can I increase the stack and the heap in java? I'm using BlueJ.

========

EDIT:

Here is the code:

// ***** Quick-Sort Method *****

public static void quickSort(int[] data, int first, int n)
{
    int p, n1, n2;
    if(n > 1)
    {
        p = partition(data, first, n);
        n1 = p - first;
        n2 = n - n1 - 1;
        quickSort(data, first, n1);
        quickSort(data, p+1, n2);
    }
}

// ***** PRIVATE HELPER FUNCTIONS *****

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

private static int partition(int[] A, int first, int n )
{
    int right = first + n - 1;
    int ls = first;
    int pivot = A[first];
    for(int i = first+1; i <= right; i++)
    {
        if(A[i] <= pivot)
        // Move items smaller than pivot only, to location that would be at left of pivot
        {
            ls++;
            swap(A, i, ls);
        }
    }
    swap(A, first, ls);
    return ls;
}

private static void swap(int[] data, int pos1, int pos2)
{
    int temp = data[pos1];
    data[pos1] = data[pos2];
    data[pos2] = temp;
}

I don't think so, I looked into google and the same problem heppened many times — Eng.Fouad, May 19 '11 at 21:10
@Eng: If your quicksort isn't approximately dividing the size by two on every iteration (which I'll bet it isn't), something's wrong with it. Double-check your algorithm. I'd bet your partition is just splitting the list into 1 less element each time. — user541686, May 19 '11 at 21:11
How big is the dataset that you're attempting to quicksort? Is it almost sorted to begin with? Did you write your own quicksort? Increasing the stack size without first determining what's actually going on is a really bad idea. — dlev, May 19 '11 at 21:12
You probably have a bug in your alogrithm resulting in an infinte recursion which shows up as a stack overflow error. Paste your code and we'll be able to help you. — Codo, May 19 '11 at 21:12
@finnw well this is a uni-assignment to measure the execution time of many sorting methods upon large amount of inputs (1000000 int) — Eng.Fouad, May 19 '11 at 21:13
@dlev: Doesn't matter how big the data set is, the depth needed decreases *exponentially*. A depth of 100 means 2^100 bytes of data for overflow, which I'd bet a million bucks he doesn't have. — user541686, May 19 '11 at 21:13
If you are dividing your dataset in two on each recursion, your stack depth should be log2(n) so for a maximum array or list, the largest depth should be 32. — Peter Lawrey, May 19 '11 at 21:14
@Mehdrad that's true only if he's using a properly written version of quicksort with data that isn't already or almost-already sorted. I suppose I hit those other two points after, so the size question is largely redundant. — dlev, May 19 '11 at 21:16

score 6 · Answer 1 · answered May 19 '11 at 21:14

6

Trying to increase the stack size due to an overflow, would be like buying more rubbish bins, when your bin is full instead of taking it to the dump.

Most probably you go into an endless recursion. Could you post your code?

answered May 19 '11 at 21:14

Hyperboreus

822
5
4

For short lists your code is fine. For large lists you should de-recursify your algorithm thus avoiding the bombardement of the stack. Keep in mind that a list with n members, will cause up to 2n-1 recursions. – Hyperboreus May 19 '11 at 21:30
On which JavaVM are you running it and how long is your list. A list with 100000 items is no problem on my VM. – Hyperboreus May 19 '11 at 21:36
On my VM I'm able to sort lists with 10 million members without issue. Are you running in a particularly constrained environment? – dlev May 19 '11 at 21:38
@div & @Hyperboreus How can I change my JavaVM – Eng.Fouad May 19 '11 at 21:56
By installing another. There are various implementations. Which one are you using. Call java -version and post the result. – Hyperboreus May 19 '11 at 21:59
@Hyperboreus Where should I call java -version ? – Eng.Fouad May 19 '11 at 22:48
On your shell. Be it sh, bash, cmd.exe, whatever shell you are using. – Hyperboreus May 20 '11 at 13:25

CRM · Accepted Answer · 2011-05-19T23:14:11.223

2

You can use the following JVM options:

-Xms initial java heap size
-Xmx maximum java heap size
-Xss Set thread stack size

If you want to set these options by default in BlueJ, you need to do the following:

Find bluej.defs file
Find bluej.vm.args property (line) within that file
Add the option that you want in that line, i.e. bluej.vm.args = -Xmx512m to set the heap size to a maximum of 512 MB.

I hope this helps.

edited May 19 '11 at 23:14

answered May 19 '11 at 21:10

CRM

4,569
4
27
33

@bacchus No, how can I do that ? – Eng.Fouad May 19 '11 at 22:42
How can I check my stack size? – Eng.Fouad May 19 '11 at 23:52
You can check the stack trace and more memory information using JConsole which is installed with the jdk. – CRM May 20 '11 at 00:27
@bacchus hmm, How can I increase the stack size in eclipse ? – Eng.Fouad May 20 '11 at 01:02
@Eng.Fouad Add the option that you want to `eclipse.ini` file. – CRM May 20 '11 at 11:03

score 1 · Answer 3 · answered May 19 '11 at 21:12

1

The stackoverflow error is usually because of a bad recursive call. Are you sure you're not doing anything wrong like specifying proper exit paths (aka terminating conditions ) for your recursion flow?

answered May 19 '11 at 21:12

Kal

24,724
7
65
65

score 0 · Answer 4 · answered May 19 '11 at 22:01

to me it looks like it's the partition that's bugged

private static int partition(int[] A, int first, int n )
{
    int right = first + n-1;
    int ls = first;
    int pivot = A[right];//use right most for pivot
    for(int i = first;i<right;i++)
    {
        if(A[i]<pivot){
           swap(A,i,ls);
           ls++;//inc after swap
        }

    }
    swap(A,right,ls);
    return ls;
}

I got this code from wikipedia

score 0 · Answer 5 · answered May 20 '11 at 00:06

The simplest implementation of Quicksort is vulnerable to O(N) memory use in the worst case. It is possible to modify it to use O(log N) in the worst case, by only recursing into the smaller subarray and by turning the remaining recursion into a while loop:

//the following code probably contains of-by-one errors

quicksort(xs, begin, end):
    while(not empty list){
        mid = partition(xs, begin, end)
        if( mid-begin < end-mid){
            quicksort(xs, begin, mid)
            end = mid
        }else{
            quicksort(xs, mid, end)
            begin = mid
        }

Got stackoverflowerror when using quickSort, can I increase the stack and the heap?

5 Answers5

Linked