stack overflow with quicksort implementation

Question

I'm trying to implement the quicksort algorithm (in C#),here's my code:

public static void sort(ref int[] A)
{
    if (A.Length==0 || A.Length==1) 
    { 
        return; 
    }
    quickSort(ref A,0,A.Length-1);
}

private static void quickSort(ref int[] A, int left, int right)
{
    if (left >= right || left < 0 || right < 0) 
        return;

    int pivot = A[left];

    int i = left - 1;
    int j = right + 1;

    while (true) 
    {
        do 
        { 
            i++; 
        } 
        while (A[i] < pivot);

        do 
        { 
            j--; 
        } 
        while (A[j] > pivot);

        if (i >= j) 
            break;

        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

    quickSort(ref A,left,j);
    quickSort(ref A, j + 1, right);
}

This algorithm works fine, however something seems illogical, I chose pivot to be equal to A[left] then in the while(true) loop I wrote do{i++}while(A[i]<pivot), I now noticed that the first time it's going to increment i so A[i] will become equal to A[left] which is the pivot value, so that should mean this do while loop will stop after the first increment of i, so when I tried to add the = operator to the while so that it won't stop after the first increment: while(A[i]<=) I got a stack overflow exception (also got the stack overflow exception when I added the equal operator to the the 2nd do while: while(A[j]>=pivot)), and I can't understand why this happened, anyone can explain please?

Note that `ref` is unnecessary, since you never assign to the variable `A`. (`ref` affects variables, not values.) — Ry-, Oct 24 '19 at 18:58
we'll I'll have to keep it since my teacher put it, but I'd love to know what you mean by "ref affects variables,not values" @Ry- — Daniel_Kamel, Oct 24 '19 at 18:59
@DanielK [see](https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/ref) there. — Trevor, Oct 24 '19 at 19:02
@EdPlunkett yes my code works fine, it's when I add the ```=``` operator to 1 of the two ```while``` inside the ```while(true)``` that it stops working and give me a stack overflow exception — Daniel_Kamel, Oct 24 '19 at 19:07
Now I see what you mean. I couldn't follow your last paragraph originally and skipped it. Now I still can't understand it. Actually I don't understand "add the = operator to 1 of the two while inside the while(true)" either. — 15ee8f99-57ff-4f92-890c-b56153, Oct 24 '19 at 19:07
good time to learn about debugger. when it throws stack overflow exception go one stack above and see if the local values is what you expected. If not then you are most likely in an infinite loop (recursion) — Steve, Oct 24 '19 at 19:58
`StackOverflowException` is always the same thing: some method in your program is calling itself, either directly, or indirectly by calling some other method that eventually calls the original one again. The debugger will usually show you a valid stack trace, but that's usually not needed, as in this case. Just step through with the debugger and when your method calls itself in a way that doesn't make forward progress (i.e. fails to reduce the partition), there's your bug. See marked duplicates, and take this opportunity to learn to use the debugger and SO's search feature. — Peter Duniho, Oct 25 '19 at 04:57

rcgldr · Accepted Answer · 2019-10-25T08:32:56.390

This is Hoare partition scheme. The do while loops need to use < or >, not <= or >=, since they rely on finding the pivot or elements equal to the pivot in stop the loops and prevent the loops from going beyond the bounds of the range [lo, hi]. Normally the middle element is used as a pivot, such as

    int pivot = A[(left+right)/2];   // or A[left + (right-left)/2]

With the current code, the only element that can't be used for pivot is A[right], since that will lead to stack overflow (the quicksort call will end up stuck with high = low + 1).

So using pivot = A[left], the first do while stops with i == left, and the second do while stops with j <= right. If i < j, then a swap occurs, swapping the pivot to A[j] and an element <= pivot to A[i == left]. Each swap prevents the next pair of do whiles from running past the bounds [low, high], so only a check for i >= j is needed after the pair of do whiles to check for partition step done.

Choosing the middle element for pivot helps for certain data patterns such as already sorted data or reverse sorted data. Still, the first do while is going to stop on the first loop if the left element == pivot.

Note that Hoare partition scheme only splits the partition into elements <= pivot and elements >= pivot. The pivot or any element equal to the pivot can end up anywhere after a partition step. This isn't an issue as eventually the pivot or elements equal to the pivot will end up in the correct position (which may not occur until a level of recursion is reached where low == high).

but when I use ```while( A[i] < pivot)``` doesn't that mean that the first time the ```do while``` will increment ```i``` by 1 so that means ```i``` will become equal to ```left``` so ```A[i]``` will be equal to ```A[left]``` which is equal to pivot, doesn't that mean that this ```do while``` will stop after the first increment, so how is it possible that the algorithm is working? — Daniel_Kamel, Oct 25 '19 at 08:11
@DanielK - I updated my answer to explain that yes, it will stop the first time if pivot = A[left], or if A[left] == pivot. This isn't a problem, since the pivot will get swapped to A[j] (unless i >=j the first time). — rcgldr, Oct 25 '19 at 08:25

stack overflow with quicksort implementation

1 Answers1