CODEWITHSUNDEEP
c++sortingstackquicksort
user6348275
user6348275

Reputation: 23

QUICK SORT stack overflow c++ big numbers

good day I am trying to use quick sort with 10000 numbers but it is giving me stack overflow error. it works with random numbers but it does not with descending and ascending numbers.

' thank you

void quickSort(long* array, long start, long last)
{
    if (start < last)
    {
        int p = partition(array, start, last);
        quickSort(array, start, p-1);
        quickSort(array, p + 1, last);
    }
}
int partition(long* array, long start, long last)//first partition
{
    int j = start + 1;
    for (long i = start + 1;i <= last;i++)
    {
        if (array[i] < array[start])
        {
            swap(array[i], array[j]);
            j++;
        }           

    }
    swap(array[start], array[j - 1]);
    return j - 1;
}
'

Upvotes: 2

Views: 1063

Answers (3)

jxh
jxh

Reputation: 70502

For sorted elements, you can avoid this problem by choosing the median of the three elements array[start], array[last] and array[(start + last + 1)/2] as your pivot value.

int median_of_3(long* array, long start, long last)
{
    long a = (start + last + 1)/2, b = start, c = last;
    if (array[c] < array[a]) swap(array[c], array[a]);
    if (array[b] < array[a]) swap(array[b], array[a]);
    if (array[c] < array[b]) swap(array[c], array[b]);
    return partition(array, start, last);
}

An additional strategy to avoid a large stack depth is to calculate which partition is smaller, and recursively call the smaller one. The other partition can then be optimized into a loop (tail recursion optimization).

void quickSort(long* array, long start, long last)
{
    if (start >= last) return;

    int p = median_of_3(array, start, last);
    int next_start[2] = { start, p + 1 };
    int next_last[2] = { p - 1, last };
    bool i = p > (start + last)/2;
    quickSort(array, next_start[i], next_last[i]);
    /*
     * If the compiler does not optimize the tail call below into
     * a loop, it is easy to do the optimization manually.
     */
    quickSort(array, next_start[!i], next_last[!i]);
}

Introspection can also be used to avoid a large stack depth. You track your recursive call depth, and if it is "too deep", you fail safe into a different sorting strategy, like merge sort or heap sort. This is the behavior currently used by std::sort.

void introSortImpl(long* array, long start, long last, int depth)
{
    if (--depth == 0) {
        heapSort(array, start, last);
        return;
    }

    if (start >= last) return;

    int p = median_of_3(array, start, last);
    int next_start[2] = { start, p + 1 };
    int next_last[2] = { p - 1, last };
    bool i = p > (start + last)/2;
    introSortImpl(array, next_start[i], next_last[i], depth);
    introSortImpl(array, next_start[!i], next_last[!i], depth);
}

void introspectionSort(long* array, long start, long last)
{
    introSortImpl(array, start, last, log2(start - last) * 3);
}

Upvotes: 3

rcgldr
rcgldr

Reputation: 28941

Example of Lomuto partition scheme like quicksort that uses recursion on the smaller partition, updates l or r, then loops back to split the larger partition into two partitions, repeating the process. Worst case stack space is O(log2(n)) which should avoid stack overflow. Worst case time complexity is still O(n^2) (depending on how partition is implemented).

Some call this example a half recursion. It's not an example of tail recursion, since tail recursion means that the recursive function just returns after calling itself. The second call in the original question example is a tail call.

void quicksort(int * tab, int l, int r)
{
   int q;
   while(l < r)
   {
      q = partition(tab, l, r);
      if(q - l < r - q) {     // recurse into the smaller partition
         quicksort(tab, l, q - 1);
         l = q + 1;
      } else {
         quicksort(tab, q + 1, r);
         r = q - 1;
      }
   }                          // loop on the larger partition
}

Upvotes: 0

hedgie
hedgie

Reputation: 71

the code is okay but your compiler uses stack very ineffectively. you just need to raise reserved stack amount. it happens much more often in debug profiles rather than release ones just because compiler preserves large stack chunks to check if stack was broken during execution of your procedure.

Upvotes: 0

Related Questions