Quick Sort not sorting numbers of high range

Question

void quickSort(vector<long>& numberList,long low, long high){
    long pivot, indexLow, indexHigh, temp;

    if(low<high){
        pivot = low;
        indexLow = low;
        indexHigh = high;

        while(indexLow<indexHigh){
            while(numberList[indexLow] <= numberList[pivot]){
            indexLow++;
            }
            while(numberList[indexHigh] > numberList[pivot]){
            indexHigh--;
            }

            if(indexLow<indexHigh){
                temp = numberList[indexLow];
                numberList[indexLow] = numberList[indexHigh];
                numberList[indexHigh] = temp;
                }
        }

        temp = numberList[pivot];
        numberList[pivot] = numberList[indexHigh];
        numberList[indexHigh] = temp;

        quickSort(numberList, low, indexHigh-1);
        quickSort(numberList, indexHigh+1, high);
    }
}

This code perfectly sorts a given list of numbers upto 10000 but I tried with 100000 and the program gets terminated, can you please tell me what I am doing wrong ?

Answer 1

While it may be stack overflow like others have said, I doubt it. Your code has a few bugs which may cause it to access out of bound positions in the array, which will (likely, though not guaranteed) prompt early termination with Segmentation Fault (or maybe it appears to work fine in other cases, that's why UB is so bad).

Consider this:

while(numberList[indexLow] <= numberList[pivot]){
    indexLow++;
}
while(numberList[indexHigh] > numberList[pivot]){
    indexHigh--;
}

What if every number in the array is already less than or equal to numberList[pivot]? indexLow will be happily incremented past high, which quite possibly is the size of the array. You need to check in both loops that the outer loop condition still remains. So, do this instead:

while (indexLow < indexHigh && numberList[indexLow] <= numberList[pivot]) {
    indexLow++;
}
while (indexHigh > indexLow && numberList[indexHigh] > numberList[pivot]) {
    indexHigh--;
}

This ensures that the inner loops do not invalidate the outer condition; without this, all bets are off as to why your code is breaking / not working.

Then we have this:

temp = numberList[pivot];
numberList[pivot] = numberList[indexHigh];
numberList[indexHigh] = temp;

Now, if you fix the loops as I said, this can be problematic. The loops may have stopped because every element is less than or equal to the pivot (and in that case it is safe to do this swap operation), but the loops may have stopped because indexLow and indexHigh collided, and in that case we don't know if numberList[indexLow] is actually greater than the pivot or if it is still less than or equal to the pivot. So we need to test it manually, and possibly decrement indexLow to find the value to swap the pivot with:

assert(indexLow == indexHigh);
assert(indexLow > low);

if (numberList[indexLow] > numberList[pivot])
    indexLow--;

assert(numberList[indexLow] <= numberList[pivot]);

temp = numberList[pivot];
numberList[pivot] = numberList[indexLow];
numberList[indexLow] = temp;

quickSort(numberList, low, indexLow-1);
quickSort(numberList, indexLow+1, high);

Here's the full version with these fixes:

void quickSort(vector<long> &numberList, long low, long high) {
    long pivot, indexLow, indexHigh, temp;
    if (low<high) {
        pivot = low;
        indexLow = low;
        indexHigh = high;

        while (indexLow < indexHigh) {
            while (indexLow < indexHigh && numberList[indexLow] <= numberList[pivot]) {
                indexLow++;
            }
            while (indexHigh > indexLow && numberList[indexHigh] > numberList[pivot]) {
                indexHigh--;
            }

            if (indexLow < indexHigh) {
                temp = numberList[indexLow];
                numberList[indexLow] = numberList[indexHigh];
                numberList[indexHigh] = temp;
            }
        }

        assert(indexLow == indexHigh);
        assert(indexLow > low);

        if (numberList[indexLow] > numberList[pivot])
            indexLow--;

        assert(numberList[indexLow] <= numberList[pivot]);

        temp = numberList[pivot];
        numberList[pivot] = numberList[indexLow];
        numberList[indexLow] = temp;

        quickSort(numberList, low, indexLow-1);
        quickSort(numberList, indexLow+1, high);
    }
}

Note that this implementation is unnecessarily more complex than usual. You don't really gain much by moving backwards and forwards in the array like that. The traditional implementation is much simpler to code and easier to read and understand:

void quicksort_simpler(vector<long> &numberList, long low, long high) {
    if (low >= high)
        return;

    long pivot = low;
    long last = pivot;
    long i;

    for (i = pivot+1; i <= high; i++) {
        if (numberList[i] <= numberList[pivot]) {
            last++;
            swap(numberList[last], numberList[i]);
        }
    }

    swap(numberList[last], numberList[pivot]);

    quicksort_simpler(numberList, low, last-1);
    quicksort_simpler(numberList, last+1, high);
}

Make sure to include <algorithm> to get the declaration for swap().

Answer 2

There's definitely a bug in your program somewhere: http://ideone.com./W0Chni

I'm only sorting the 10 elements 2-1-3-8-1-6-8-9-9-9 and it ends up with an indexLow of 11 shortly before crashing.

Sorry my fault, it works fine.

I echo that it's probably a stack overflow. You can mitigate the likelyhood somewhat by taking a different pivot (you should anyway), but the best way is to avoid a stack overflow is to use a stack data-structure instead of recursion:

1. Push your initial {low,high} onto the stack
2. Wrap your function in a while loop until the stack is empty. Each iteration pop the top {low,high} off the stack.
3. Instead of recursing, you push pairs of {low,high} onto the stack.

Like this: http://ideone.com/gwWSjV

void quickSort(std::vector<long>& numberList, long low, long high)
{
    struct lh { long low; long high; };
    std::vector<lh> stack;
    stack.push_back(lh{low, high});

    while (!stack.empty())
    {
        lh popped = stack.back();
        stack.pop_back();
        low = popped.low;
        high = popped.high;

        long pivot, indexLow, indexHigh, temp;

        if(low<high){
            pivot = low;
            indexLow = low;
            indexHigh = high;

            while(indexLow<indexHigh){
                while(numberList[indexLow] <= numberList[pivot]){
                indexLow++;
                }
                while(numberList[indexHigh] > numberList[pivot]){
                indexHigh--;
                }

                if(indexLow<indexHigh){
                    temp = numberList[indexLow];
                    numberList[indexLow] = numberList[indexHigh];
                    numberList[indexHigh] = temp;
                    }
            }

            temp = numberList[pivot];
            numberList[pivot] = numberList[indexHigh];
            numberList[indexHigh] = temp;

            //quickSort(numberList, low, indexHigh-1);
            stack.push_back(lh{low, indexHigh-1});

            //quickSort(numberList, indexHigh+1, high);
            stack.push_back(lh{indexHigh+1, high});
        }
    }
}

Voilà: no more recursion, sorts 1,000,000 elements with no trouble at all.

You can optimise it by only pushing the 2nd recursion onto the stack and then immediately looping back to execute the first without push/pop, but it's not a huge gain.

Answer 3

Its very important for quicksort to take a good pivot. You are taking 1st element (your low actually):

pivot = low;

So as a result you are getting recursion with depth like 100000, so its Stack Overflow.

Answer 4

For 10^5 number of elements, there is too many recursive routine calls which will exceed function stack capacity and cause stack overflow. Like for worst case of quick sort (when all the elements are sorted already O(n^2)), the recurrence relation is T(n) = T(n - 1) + Θ(n) which will definitely cause stack overflow. Actually, 10^5 is large enough to cause stack overflow in best/average case too (O(n logn)). Use iterative method for quick sort instead if your container is too large.