CODEWITHSUNDEEP
javaarraysrecursionquicksort
proah
proah

Reputation: 354

Recursion calls overflows stack

I'm having a problem with the partitioning while trying to implement the Quicksort algorithm. My implementation works good with arrays up to a size of 10,000 but over that I'm getting a StackOverflowError. Note that this only happens when the input arrays are in a/descending order. Random-ordered arrays can be up to 10,000,000,000 before they cause the same issue.

I'm pretty sure that there is something wrong in the part when I'm partitioning the array, but I can't really see what's wrong. I've tried debugging but had no success with finding the issue. I understand that the error is caused by too many recursive calls but as far as I know, the stack shouldn't overflow if the partitioning is well implemented.

Thanks in advance :)

My code:

public void sort(int[] v, int first, int last) {


    if (first >= last) return; 
    //less than two elements left in subvector

    // Partition the elements so that every number of
    // v[first..mid] <= p and every number of v[mid+1..last] > p.
    int[]subvector = new int[2];

    subvector = partition(v, first, last);

    sort(v, first, subvector[0]-1);
    sort(v, subvector[1], last);

}

And the partitioning method:

private int[] partition(int[] v, int first, int last) {
    int low = first;
    int mid = first;
    int high = last;
    int pivot = getPivot(v, last);


    while (mid <= high) {
        // Invariant:
        //  - v[first..low-1] < pivot
        //  - v[low..mid-1] = pivot
        //  - v[mid..high] are unknown
        //  - v[high+1..last] > pivot
        //
        //       < pivot   = pivot      unknown     > pivot
        //     -----------------------------------------------
        // v: |          |          |a            |           |
        //     -----------------------------------------------
        //     ^          ^          ^           ^           ^
        //    first      low        mid         high        last
        //
        int a = v[mid];
        if (a < pivot) {
            v[mid] = v[low];
            v[low] = a;
            low++;
            mid++;
        } else if (a == pivot) {
            mid++;
        } else { // a > pivot
            v[mid] = v[high];
            v[high] = a;
            high--;
        }
    }

    return new int[]{low, high};
}

Upvotes: 0

Views: 61

Answers (1)

Ben Jackson
Ben Jackson

Reputation: 93710

Quicksort is known to be O(n^2) worst case, which is when you give it sorted input and choose the worst pivot (the highest or lowest element). That will also have the effect of causing very deep recursion, as you have seen. You don't include your pivot selection mechanism, so I can't be sure what you're doing, but you appear to select the last element. Some googling will turn up extensive discussions on pivot selection for qsort.

Upvotes: 2

Related Questions