CODEWITHSUNDEEP
c++algorithmsortingquicksort
harry0816
harry0816

Reputation: 23

Why do I get a stack overflow when I include the pivot in recursive calls in the quicksort algorithm?

I am trying to implement the quicksort algorithm in c++ as a project in a lecture. The program works fine when I exclude the pivot from the recursive calls, but sometimes causes a stack overflow error when i include the pivot in either of the recursive calls.

The program malfunctions only for a specific array size, but I can't figure out what relation they have with the errors. For example, the program malfunctions when I give 40, but works just fine for 50.

void quicksort(double* arr, int init, int fin) {
    if (init == fin) return;
    if (init == fin - 1) {
        if (arr[init] > arr[fin]) {
            double temp = arr[fin];
            arr[fin] = arr[init];
            arr[init] = temp;
        }
        return;
    }
    int smaller = init - 1;
    double pivot = arr[fin];
    for (int ind = init; ind < fin; ind++) {
        if (arr[ind] < pivot) {
            smaller++;
            double temp = arr[ind];
            arr[ind] = arr[smaller];
            arr[smaller] = temp;
        }
    }
    arr[fin] = arr[smaller + 1];
    arr[smaller + 1] = pivot;
    if(smaller>=init) quicksort(arr, init, smaller);
    if(smaller+2<=fin) quicksort(arr, smaller + 2, fin);
    return;
}

This is the code in question. It works fine when i put it this way, but causes errors when i replace

if(smaller+2<=fin) quicksort(arr, smaller + 2, fin);

with

if(smaller+1<=fin) quicksort(arr, smaller + 1, fin);

Upvotes: 2

Views: 120

Answers (2)

Adrian McCarthy
Adrian McCarthy

Reputation: 47962

Another way to look at it. Suppose the selected pivot element is the smallest value in the partition. It will move to the beginning of the range.

[ 3 5 2 1 4]  // supposed we select 3 as the pivot
[ 2 1 3 5 4]  // after partitioning
[ 3 5 4] // the recursive call for the right "half"

If we select 3 as the pivot again, nothing changes in this range. And thus, when we recurse on the right "half" again, we're in exactly the same situation. We've not made any progress, so recursion will continue until the stack overflows.

Omitting the pivot from the ranges for the recursive calls guarantees we make progress and thus that the recursion will eventually terminate.

Upvotes: 0

ruakh
ruakh

Reputation: 183361

if(smaller+1<=fin) is equivalent to if(true) (since smaller+1 starts out as init and is incremented at most fin-init times), so any call with at least three elements will necessarily recurse at that line — and the recursive call may not accomplish anything, if (for example) all three elements are equal.

Upvotes: 2

Related Questions