C++ Getting StackOverflow error in quicksort function

Question

I am getting stackoverflow error when I am trying to sort using quicksort an array of large size, and this array is in descending order. I want to sort it in ascending order using the code below:

int partition_lastElementPivot(int * arr, int lo, int hi)
{
    int x = arr[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; j++)
    {
        if (arr[j] <= x)
        {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[hi];
    arr[hi] = arr[i + 1];
    arr[i + 1] = temp;

    return i + 1;
}

void quicksortLastElementPivot(int*arr, int lo, int hi)
{
    if (lo<hi)
    {
        int mid = partition_lastElementPivot(arr, lo, hi);
        quicksortLastElementPivot(arr, lo, mid - 1);
        quicksortLastElementPivot(arr, mid + 1, hi);
    }
}

This code works fine when I randomly generate an array of any size, suppose of size 5000. But when I generate an array of size 5000 sorted in descending order and then try to sort using this code, I get a stackoverflow error. Does C++ limits the memory useable by stack and why is this happening.

int arr[5000];
int count = 5001;
for(int i=0; i<5000; i++)
{
    arr[i] = count;
    count--;

}
quicksortLastElementPivot(arr, 0, 4999)

Thanks

Answer 1

Quicksort has a truly dreadful worst-case performance, as you have discovered here. It is calling itself at a stack depth of 5000. This Wikipedia article has a good discussion on the subject. In particular, it mentions tail recursion as a solution to your stack overflow problem.

Briefly, this means that instead of the last call to quicksortLastElementPivot, followed immediately by a return, you just loop back to the start of the function. This has the same effect, but the tail recursion doesn't increase the stack size. For this to work, you have to make sure that the smaller of the two partitions is sorted first, using traditional recursion, and the larger partition is sorted by tail recursion. Something like this (not tested!):

void quicksortLastElementPivot(int*arr, int lo, int hi)
{
TailRecurse:
    if (lo<hi)
    {
        int mid = partition_lastElementPivot(arr, lo, hi);
        if (mid < (lo + hi) / 2)
            { // First partition is smaller
            quicksortLastElementPivot(arr, lo, mid - 1); // Sort first partition
            lo = mid + 1; goto TailRecurse;              // Sort second partition
            }
        else
            { // Second partition is smaller
            quicksortLastElementPivot(arr, mid + 1, hi); // Sort second partition
            hi = mid - 1; goto TailRecurse;              // Sort first partition
            }
    }
}

Answer 2

C++ standard does not define the stack-size of an executable program.

This limit is typically defined in the make file or the linker-command file of your project.

Depending on your IDE, you might also find it within your project settings (under linker-configuration).

The answer given by TonyK is doing quite a good job in explaining the stack usage of quick-sort under the worst-case scenario (which is exactly the case in your code, where arr is sorted in reversed order).

Answer 3

#include <iostream>
using namespace std;

void QuickSort(int *arr, int left, int right)
{
int i = left;
int j = right;
int pivot = arr[rand() % (right - left) + left];
while (i < j)
{
    while (arr[i] < pivot)
    {
        i++;
    }
    while (arr[j] > pivot)
    {
        j--;
    }
    if (i <= j)
    {
        swap(arr[i], arr[j]);
        i++;
        j--;
    }
}
if (left < j)
{
    QuickSort(arr, left, j);
}
if (i < right)
{
    QuickSort(arr, i, right);
}
  }
  int main()
 {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int n;
cin >> n;
int *arr = new int[n];

for (int i = 0; i < n; i++)
{
    cin >> arr[i];
}
QuickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++)
{
    cout << arr[i] << " ";
}

delete arr;
}