0

My QuickSort implementation causes StackOverflow error if I give reverse-sorted array. It is working fine for about 1000 items, but for 10000+ I get StackOverflow error. If I get the error the recursion depth is about 9000. I know my algorithm always choose the latest element of the subarray as pivot, which is not optimal, but I would not change that, because I want to make it work like this. Here is the code:

private int partition(int[] numbers, int begin, int end) {
    int pivot = numbers[end];
    int partitionIndex = begin;
    for (int i = begin; i < end; ++i) {
        comparisonCounter++;
        if (numbers[i] <= pivot) {
            if (i != partitionIndex) {
                swapCounter++;
                int temp = numbers[i];
                numbers[i] = numbers[partitionIndex];
                numbers[partitionIndex] = temp;
            }
            partitionIndex++;
        }
    }
    if (partitionIndex != end) {
        swapCounter++;
        int temp = numbers[partitionIndex];
        numbers[partitionIndex] = numbers[end];
        numbers[end] = temp;
    }
    return partitionIndex;
}

private void quickSort(int[] numbers, int begin, int end) {
    if (begin < end) {
        int partitionIndex = partition(numbers, begin, end);
        quickSort(numbers, begin, partitionIndex - 1);
        quickSort(numbers, partitionIndex + 1, end);
    }
}

Is there something wrong with my implementation? How could I fix it? Thank you!

marfoldi
  • 3
  • 2
  • 1
    If the list is a reverse-sorted array, and you're always picking the last element as the pivot, it seems expected that you're going to get a recursion depth of roughly the length of the list, since one of your partitions will be empty. – Andy Turner May 22 '15 at 21:41
  • From [Wikipedia](http://en.wikipedia.org/wiki/Quicksort), "the leftmost element of the partition would often be chosen as the pivot....This causes worst-case behavior on already sorted arrays." Since you are using the last as the pivot and a reversed array, this is worst case behavior. So you don't really have a good implementation, since you will have O(n^2). You should use the middle or another element as the pivot instead. – mbomb007 May 22 '15 at 21:50
  • Thank you for both of you. Yes, I tested for the worst case, then I get the error. Now I may rewrite it to the iterative approach. – marfoldi May 22 '15 at 22:06

2 Answers2

2

Nothing seems wrong with your code but bear in mind that this is a recursive function and most languages have a limited-depth stack which you are bound to get to if you have an input large enough. For Java, see:

What you could do is turn your method, from a recursive to an iterative approach. There are several ways you can do it. I just found a couple examples online:

Community
  • 1
  • 1
Josep Valls
  • 5,483
  • 2
  • 33
  • 67
  • Thank you so much for your fast answer! As you see my implementation is ok? I just have to deal with the java stack or rewrite it to the iterative approach? – marfoldi May 22 '15 at 21:45
  • @marfoldi did not go in detail in your code but at a quick glance it looks fine. Again, the error you report is a common error in all recursive calls. If you want to just get it out of the way, try tweaking the memory allocated to the stack. If you want a more long-term solution or you want to practice your coding, go ahead and try to make your solution iterative. For any general purpose sorting though, the built in Java sorting methods provide the most reasonable and stable optimizations. – Josep Valls May 22 '15 at 22:00
0

There are some ways to reduce the stack size in Quicksort.

  • You could put the larger partition on the stack each time, leaving it there while the smaller partition is sorted first. That keeps too many small partitions from clogging up the stack at once.

  • You could use another method, such as insertion sort, to sort small partitions rather than Quicksort. Again, that keeps a lot of small partitions off the stack. You can experiment, but something in the region of 15 - 20 elements usually counts as a "small" partition.

As you say, using a better method to pick your pivot would also help.

rossum
  • 15,344
  • 1
  • 24
  • 38
  • Since there's a recent link to this, use recursion for the smaller partition, and loop back to handle the larger partition. – rcgldr Nov 06 '22 at 07:20