1

I am implementing the "QuickSort" algorithm provided through GeeksForGeeks. I am sorting an input size of 50K random numbers, I get a error message saying "StackOverFlowError". Is this a case where the recursive call doesn't know when to reach its base case? The crash is happening at line 58.

int partition(int arr[], int low, int high)
{
    int pivot = arr[high];
    int i = (low-1); // index of smaller element
    for (int j=low; j<high; j++)
    {
        // If current element is smaller than or
        // equal to pivot
        if (arr[j] <= pivot)
        {
            i++;

            // swap arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // swap arr[i+1] and arr[high] (or pivot)
    int temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;

    return i+1;
}


/* The main function that implements QuickSort()
  arr[] --> Array to be sorted,
  low  --> Starting index,
  high  --> Ending index */
void sort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[pi] is
          now at right place */
        int pi = partition(arr, low, high);

        // Recursively sort elements before
        // partition and after partition
        sort(arr, low, pi-1); // Line 58, on my IDE
        sort(arr, pi+1, high);
    }
}
Alex Brito
  • 43
  • 8
  • Crash is happening at line 58 yet you only provide 46 lines of code – Kars Mar 19 '19 at 19:17
  • did you try and have a look at https://stackoverflow.com/questions/29240519/quicksort-java-lang-stackoverflowerror ? also as @Kars mentioned try add a quick edit on the line which causes the problem – Mischiefz Mar 19 '19 at 19:18
  • 1
    Stack overflow in a recursive methof: in 19 out of 20 cases it’s caused by infinite recursion. – Ole V.V. Mar 19 '19 at 19:19
  • @Kars I just commented on the code where the crash is occurring, sorry about that. – Alex Brito Mar 19 '19 at 19:31
  • What are your starting values of low and high? You might have a problem there. – HariUserX Mar 19 '19 at 19:33
  • 2
    If the `if` condition in the `partition` method were true every time, then by the end of the loop, you have `i = high - 1`. That gives the recursive call on line 58 the same parameters as the current call, hence the stack overflow. You need to think more carefully about all the `+1` and `-1` stuff you're doing, maybe with the help of your debugger. – Dawood ibn Kareem Mar 19 '19 at 19:34
  • If all your numbers to sort all already in order (or in reverse order), your pivot will be poorly chosen and you will have 50K recursions. It says random numbers in your question. Are you sure they are? – agbinfo Mar 19 '19 at 20:09

3 Answers3

0

Is this a case where the recursive call doesn't know when to reach its base case?

This method works with smaller arrays. It would not work at all if it didn't reach the base case. So, no.

You're running out of stack size because you're keeping a copy of the array in memory for each time you enter into recursion.

Kars
  • 845
  • 1
  • 14
  • 33
  • Where exactly is he making the copy? – HariUserX Mar 19 '19 at 19:50
  • Each time you enter into recursion, Java keeps the array on the stack. So effectively each time you enter a new round of recursion you are making a copy. I used the word keeping though, do not get confused. – Kars Mar 19 '19 at 19:57
0

I don't see any problem with you code. It must be the stack size, try increasing it using

Setting it to 2 MB.

java -Xss2m QuickSort

If you are on IDE, change/add it in Run Configuration of IntelliJ/Ecllipse.

HariUserX
  • 1,341
  • 1
  • 9
  • 17
0

Java does not save arrays on stack. It saves them in heap instead. So you just copy a reference to the array in the heap and NOT an array. And when you pass arrays to methods you pass it by reference. So to your question. I have the same problem. And if you made stack size bigger it just will take longer to throw StackOverFlow. So it`s not the solution. If I will found it I will added it here.

cplusplus
  • 92
  • 8