stack overflow with quicksort implementation [duplicate]

Question

This question already has answers here:

Another Quicksort stackoverflow (3 answers)

How to avoid a stack overflow? (7 answers)

live debugging a stack overflow (6 answers)

Closed 6 years ago.

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-
– Ry- ♦, Commented Oct 24, 2019 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
– Daniel_Kamel, Commented Oct 24, 2019 at 18:59
@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
– Daniel_Kamel, Commented Oct 24, 2019 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
– Steve, Commented Oct 24, 2019 at 19:58

rcgldr · Accepted Answer · 2019-10-25 08:32:56Z

1

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).

edited Oct 25, 2019 at 8:32

answered Oct 25, 2019 at 1:56

rcgldr

29.4k3 gold badges41 silver badges70 bronze badges

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

2 Comments

Daniel_Kamel Over a year ago

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?

rcgldr Over a year ago

@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).

Collectives™ on Stack Overflow

stack overflow with quicksort implementation [duplicate]

1 Answer 1

2 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Linked

Related