CODEWITHSUNDEEP
c++quicksort
user3047841
user3047841

Reputation: 23

Why is my quicksort so inefficient?

I've made a quicksort from a variety of sources online and made mine using the technique of having the pivot in the centre and not the first or last index like some others did.

However, the sort ends up breaking my program over 80 elements as it just freezes and I'm assuming it's because it's being inefficient with memory.

The data it's trying to sort is by no way already sorted and fully random.

void swapVecPos(int posOne, int posTwo)
{
    int temp = intVec[posOne];
    intVec[posOne] = intVec[posTwo];
    intVec[posTwo] = temp;
}

void sortShit(int leftValue, int rightValue)
{
    int left = leftValue;
    int right = rightValue;
    int pivot = intVec[(leftValue + rightValue) / 2];

    while(left <= right)
    {
        while(intVec[left] < pivot)
        {
            left++;
        }

        while(intVec[right] > pivot)
        {
            right--;
        }

        if(left <= right)
        {
            swapVecPos(left, right);
            left++;
            right--;
        }
    }

    if(leftValue < right)
        sortShit(leftValue, right);

    if(left < rightValue)
        sortShit(left, intVec.size() - 1);
}

Thank you

Upvotes: 0

Views: 140

Answers (2)

Ben Voigt
Ben Voigt

Reputation: 283684

This line is wrong:

sortShit(left, intVec.size() - 1);

Some other branch of the recursion is responsible for sorting between rightValue+1 and intVec.size()-1. You only need to recurse using

sortShit(left, rightValue);

which restores the invariant that recursive calls are always on successively smaller sets, and therefore terminate.

Your call allows the size of the right-hand set to grow, and therefore doesn't guarantee termination.

Upvotes: 1

James Kanze
James Kanze

Reputation: 153919

There are two obvious errors in your code. First, if at any time the pivot is the smallest or the largest value (and that will happen at some time if the values are random), you leave the partition you're working on. If the partition is the first or the last, this may result in undefined behavior, but in any case, it will not give the right results.

Second: when you're recursing, the second recursion uses intVect.size(), so it calls the function on everything which remains. This is surely the cause of the symptom you're seeing.

Upvotes: 2

Related Questions