0

I am currently writing an algorithm to analyze the sorting algorithms. I have many inputs from 1000 numbers up to 1 000 000 inputs. Currently I'm having some problems with the Quick Sort function. As I have an input of 1 000 000 of similar numbers (numbers between 1-10) this code will throw me an error (0xC00000FD) (seems to be an stack overflow exception). Now, I don't know what to do to lower the numbers of recursion calls or how to increase the stack so there could be multiple recursion calls. I'm attaching the code for the Quick Sort.

void swap(int *xp, int *yp)
    {
        int temp = *xp;
        *xp = *yp;
        *yp = temp;
    }

int partition (int arr[], int low, int high)
{
    int pivot = arr[(low+high)/2];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}
void quicksort(int A[], int l, int h)
{
    if (l < h) {
        int p = partition(A, l, h);
        quicksort(A, l, p - 1);
        quicksort(A, p + 1, h);
    }
}
Improve this question
5
  • 1
    Aside: please replace j <= high - 1 with the more idiomatic j < high. Not only is it easier for the brain to parse, but that habit can get you into trouble when the operands are unsigned. Commented Mar 8, 2021 at 14:23
  • There are many well-known implementation pitfalls of Quicksort that lead to pessimistic behavior both in terms of running time and stack usage. Commented Mar 8, 2021 at 14:35
  • 1
    Allocating 1,000,000 elements on the stack may overflow your stack. If that is not the problem, edit your question to provide a minimal reproducible example. Commented Mar 8, 2021 at 14:39
  • Does this answer your question? QuickSort and stack overflow exception Commented Mar 8, 2021 at 14:39
  • Two recursive calls will result in a stack overflow for some less favourable inputs. The common solution is to sort the smaller partition first using recursion, and then use iteration (or tail recursion) for the larger one. See en.wikipedia.org/wiki/Quicksort#Space_complexity. Commented Mar 8, 2021 at 14:49

2 Answers 2

Reset to default
1

If you get stack overflows during recursion, it means that your recursion is broken. Recursion in general should be avoided since it has a huge potential for creating slow and dangerous algorithms. If you are a beginner programmer, then I would strongly advise to simply forget that you ever heard about recursion and stop reading here.

The only time it can be reasonably allowed is when the recursive call is placed at the end of the function, so-called "tail call recursion". This is pretty much the only form of recursion that the compiler can actually optimize and replace with an inlined loop.

If it cannot perform tail-call optimization, then it means that a function is actually called each time you do recursion. Meaning that the stack keeps piling up and you also get function call overhead. This is both needlessly slow and unacceptably dangerous. All recursive functions you ever write must therefore be disassembled for the target, to see that the code has not gone haywire.

Since this code seems to be taken from this site https://www.geeksforgeeks.org/iterative-quick-sort/, they already described most of these problems with the code for you there. They have a "quickSortIterative" function at the bottom which is a much better implementation.

My take is that the aim of the tutorial is to show you some broken code (the code in your question) then demonstrate how to write it correctly, by getting rid of the recursion.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Thank you for your detailed answer. To quickly response to your assumption, yes, I am a beginner in coding. I tried to implement the iterative form of the algorithm but it seems like the same error occurred Process finished with exit code -1073741571 (0xC00000FD).
@Iliuta-LaurentiuAndoni The geeksfor implementation got a different kind of stack weakness, namely it will allocate a big variable-length array on the stack. If you grab their implementation from the link then replace int stack[h - l + 1]; with int* stack = malloc(sizeof(int[h - l + 1]));, the problem might go away.
The proposed iterative implementation is not much better than anything. It is totally broken. It uses O(n) extra space. A non-broken implementation uses O(log n).
@n.'pronouns'm. Extra temporary space is a non-issue on modern computers. Besides, the recursive version doesn't store its data in thin air either, as evident by the stack overflow. "Big O" is mostly irrelevant too when dealing with cache memory, what really matters is how frequent an algorithm touches adjacent memory cells and the number of branches in the algorithm. Brute force search/sort algorithms may very well outperform algorithms that should in theory be much faster.
@n.'pronouns'm. Heh, well if you put it to the extremes like that :) But the algorithm should only need to allocate memory to cover the maximum call stack depth.
1

Stack overflow can be avoided by only recursing on the smaller partition:

void quicksort(int A[], int l, int h)
{
    while (l < h) {
        int p = partition(A, l, h);
        if((p - l) <= (h - p)){
            quicksort(A, l, p - 1);
            l = p + 1;
        } else {
            quicksort(A, p + 1, h);
            h = p - 1;
        }
    }
}

However, worst case time complexity remains at O(n^2), and the Lomuto partition scheme used in the questions code has issues with a large number of duplicate values. Hoare partition scheme doesn't have this issue (in fact more duplicates results in less time).

https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme

Example code with partition logic in quicksort:

void quicksort(int a[], int lo, int hi)
{
    int p;
    int i, j;
    while (lo < hi){
        p = a[lo + (hi - lo) / 2];
        i = lo - 1;
        j = hi + 1;
        while (1){
            while (a[++i] < p);
            while (a[--j] > p);
            if (i >= j)
                break;
            swap(a+i, a+j);
        }
        if(j - lo < hi - j){
            quicksort(a, lo, j);
            lo = j+1;
        } else {
            quicksort(a, j+1, hi);
            hi = j;
        }
    }
}
Improve this answer

5 Comments

this is still O(n^2) worst case, correct? the wording here is a bit confusing in this regard. or perhaps such a case will be exceedingly rare?
@WillNess - worst case time complexity remains at O(n^2), but worst case stack space is O(log2(n)).
re the stack, yes, that is clear.
@WillNess - the strategy is to only push indexes for the smaller partition, and loop back for the larger partition. The worst case stack space occurs when every split evenly splits a partition into equal sizes.
right. or actually, you meant it the other way around (as you already do here) . :)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.