0

Good day! I am getting a StackOverflowError when running my quickSort algorithm. This error occurs when elements in the array > 50 000.

My code is below :

public void recQuickSort(int left, int right)
{
    if(right-left <= 0)
        return;
    else {
        long pivot = a[right];
        int partition = partitionIt(left, right, pivot);
        recQuickSort(left, partition-1);  
        recQuickSort(partition+1, right); 
    }
}
public int partitionIt(int left, int right, long pivot) {
    int leftPtr = left - 1;
    int rightPtr = right;
    while (true) {
        while (a[++leftPtr] < pivot) ;
        while (rightPtr > 0 && a[--rightPtr] > pivot) ;
        if (leftPtr >= rightPtr)
            break;
        else
            swap1(leftPtr, rightPtr);
    }
        swap1(leftPtr, right);
        return leftPtr;
}

public void swap1(int dex1, int dex2)  // Permutation of two elements
{
    long temp;
    temp = a[dex1];
    a[dex1] = a[dex2];
    a[dex2] = temp;
}

How can I fix this error when elements > 50 000?

andrewgazelka
  • 1,746
  • 1
  • 16
  • 26
Nikolai Neverov
  • 25
  • 2
  • 8
  • 1
    This is an inherent problem with all recusrive algorithms. You will eventually run out of stack memory. A partial fix for Java is given [here](https://stackoverflow.com/questions/3700459/how-to-increase-the-java-stack-size), but with input sizes large enough, you will always be able to produce a `StackOverflowException`. – Turing85 Dec 24 '17 at 21:54
  • 1
    You're using recursive functions, splitting your input in half each time. With `50,000` elements you're looking at a best-case stack depth of around `log_2(50000) ~= 16`. In the worst case, a stack depth of `50000`. This is very vulnerable to stack overflows. – hnefatl Dec 24 '17 at 21:57
  • 1
    Possible duplicate of [How to increase the Java stack size?](https://stackoverflow.com/questions/3700459/how-to-increase-the-java-stack-size) – Turing85 Dec 24 '17 at 21:57
  • It might be an off-by-one error, which results in unexpected long stack depths. Please use a debugger and check the input values and variables, if they are at the correct index position where they are supposed to be. – Progman Dec 24 '17 at 22:10

1 Answers1

1

Only recurse on the smaller partition, then update left or right and loop back for the larger partition. This will prevent stack overflow (limit to log2(n) stack frames), but won't prevent worst case time complexity O(n^2).

public void recQuickSort(int left, int right)
{
    while(true){
        if(right-left <= 0)
            return;
        else {
            long pivot = a[right];
            int partition = partitionIt(left, right, pivot);
            if((partition - left) <= (right - partition)){
                recQuickSort(left, partition-1);
                left = partition+1;
            } else {
                recQuickSort(partition+1, right);
                right = partition-1;
            }
        }
    }
}
rcgldr
  • 27,407
  • 3
  • 36
  • 61