Got stackoverflowerror when using quickSort, can I

问题:

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

回答1:

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.

回答2:

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?

回答3:

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?

回答4:

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

回答5:

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
        }