CODEWITHSUNDEEP
c++stack-overflowquicksort
NPS
NPS

Reputation: 6355

Quicksort causing stackoverflow?

This is my implementation of quicksort:

int choosePivotIndex(int l, int r)
{
    return l + rand() % (r + 1 - l);
}

void swap(int a[], int l, int r)
{
    int tmp = a[l];
    a[l] = a[r];
    a[r] = tmp;
}

int partition(int a[], int l, int r)
{
    int p = choosePivotIndex(l, r);
    swap(a, p, r);
    int d = l;
    for (int i = l ; i < r ; ++i)
    {
        if (a[i] < a[r])
        {
            swap(a, i, d);
            ++d;
        }
    }
    swap(a, d, r);
    return d;
}

void quickSort(int a[], int l, int r)
{
    if (l < r)
    {
        int p = partition(a, l, r);
        quickSort(a, l, p - 1);
        quickSort(a, p + 1, r);
    }
}

void quickSort(int a[], int len)
{
    srand(static_cast<unsigned int>(time(nullptr)));

    quickSort(a, 0, len - 1);
}

I use it like so:

int a[10];
quickSort(a, 10);

It seems to work fine for small arrays but when I provide it with a big one (e.g. 300 000 elements) I get a stack overflow error. I tried to remedy it by using recursion only on the smaller part and sorting the bigger one in a while loop:

void quickSort(int a[], int l, int r)
{
    while (l < r)
    {
        int p = partition(a, l, r);
        if (p - l < r - p)
        {
            quickSort(a, l, p - 1);
            l = p + 1;
        }
        else
        {
            quickSort(a, p + 1, r);
            r = p - 1;
        }
    }
}

But I get the same results. Have I done something wrong? How can I make it work for bigger arrays?

Upvotes: 1

Views: 108

Answers (1)

Samer Tufail
Samer Tufail

Reputation: 1894

As per the discussions in the comments section the code appears to be fine and the offending part would be the declaration of the array on the stack

int a[10];

Where this is fine for smaller arrays its easy to run into a stack overflow with large arrays, to test this you could declare a large array of int a[1000000] and without the quicksort code you would still get a stack overflow. It is therefore recommended to declare them on the heap by doing a new

Upvotes: 2

Related Questions