0

I'm getting a Stackoverflow if I try this code with numbers.length n = 100.000 ("." just for readability) and numbers being in inverse order so like 100.000 99.999 99.998 ... Is that normal? It works for smaller n like 10.000.

private void quickSort(int[] numbers, int l, int r) {
    if (l < r) {
      int p = numbers[r];
      int i = l - 1;
      int j = r;
      do {
        do {
          i++;
        } while (numbers[i] < p);
        do {
          j--;
        } while (j >= l && numbers[j] > p);
        if (i < j) {
          swap(numbers, i, j);
        }
      } while (i < j);
      swap(numbers, i, r);
      quickSort(numbers, l, i - 1);
      quickSort(numbers, i + 1, r);
    }
  }
Vadim Kotov
  • 8,084
  • 8
  • 48
  • 62
John Doe
  • 173
  • 2
  • 10
  • I guess you are exceeding the recursion depth - even though that should not happen on logarithmic depth... – Matthias Bö May 31 '18 at 17:37
  • You're always taking the rightmost element as the pivot. When the input is already sorted, that's a bad choice. –  May 31 '18 at 17:38
  • Thanks Wumpus Q. Wumbley thats it if the numbers are random its no problem! – John Doe May 31 '18 at 17:42

1 Answers1

0

You are probably making too many recursive calls, because the array is already sorted. You can allow JVM to use up more memory or change the maximum recursive depth. A better solution is to implement a non-recursive quicksort. Here's a Java example.

AndrejH
  • 2,028
  • 1
  • 11
  • 23
  • How could I allow more memory to the JVM? – John Doe May 31 '18 at 17:46
  • Take a look at this https://stackoverflow.com/questions/2294268/how-can-i-increase-the-jvm-memory – AndrejH May 31 '18 at 17:51
  • Other standard resolutions would be: take the middle element instead of one of the ends as the pivot; or, if you're paranoid about the more unlikely worst case being a fixed case, pick a random element as the pivot. – Daniel Schepler May 31 '18 at 17:53