Search code examples
c++sortingvectorquicksortstdvector

The variable I initialised as 0 randomly turns into a -1?


I am trying to make vector based QuickSort implementation. However I ran into an out of range exception and I cannot figure out whats wrong with my code.

void myQuicksort(std::vector<int>& values, int first, int last);

int largest(std::vector<int>& values)
{
    //using Quicksort
    int first = 0;
    int last = values.size() - 1;
    myQuicksort(values, first, last);
    return values[last-1];
    
}

void myQuicksort(std::vector<int>& values, int first, int last)
{
    int cnt1, cnt2, pivot, Temporary;
    if (first < last)
    {
        pivot = first;
        cnt1 = first;
        cnt2 = last;
        while (cnt1 < cnt2)
        {
            while (values[cnt1] <= values[pivot] && (cnt1 < last))
            {
                cnt1++;
            }
            while (values[cnt2] > values[pivot])
            {
                cnt2--;
            }
            if (cnt1 < cnt2)
            {
                Temporary = values[pivot];
            }
        }
        Temporary = values[pivot];
        values[pivot] = values[cnt2];
        values[cnt2] = Temporary;
        myQuicksort(values, first, cnt2 - 1);
        myQuicksort(values, cnt2 - 1, last);
    }
}

int main()
{
    std::vector<int> signature = { 0,21,34,55,8,13,1,1,2,3,5 };
    std::cout << largest(signature)<<std::endl; 
}

I used the debugger to find the "first" variable got reassigned as a -1. There are no clues as to why this happened. This lead to an out of range exception.


Solution

  • As pointed out by Thomas Sablik and Andreas Wenzel, the main problem is in the second call to myQuickSort() and it should be

    std::swap(values[pivot], values[cnt2]);
    myQuicksort(values, first, cnt2 - 1);
    myQuicksort(values, cnt2 + 1, last);   // <-- passing cnt2 - 1 here discarded the pivot
    

    because you just swapped values[cnt2] and values[pivot], placing the pivot of this iteration at the correct place, ie cnt2.
    Therefore the next iterations must avoid cnt2 and run before and past it

    Both these comparisons must be less than equal rather than just less than

    // If only this comparison is <= the loop doesn't end
    while (cnt1 <= cnt2)
    {
        // If only this comparison is <= it doesn't sort correctly
        while (values[cnt1] <= values[pivot] && (cnt1 <= last))
    

    Andreas Wenzel also noted that in the block under if (cnt1 < cnt2) the code doesn't actually do anything. To me it seems that you started writing the swap and just forgot to complete it :)
    Anyway, this is a fixed version.

    void myQuicksort(std::vector<int>& values, int first, int last)
    {
        if (first >= last)
            return;
    
        int cnt1 = first;
        int cnt2 = last;
        int pivot = first;
    
        while (cnt1 <= cnt2)
        {
            while (values[cnt1] <= values[pivot] && (cnt1 <= cnt2)) // It just needs to go to cnt2, not last
                cnt1++;
    
            while (values[cnt2] > values[pivot])
                cnt2--;
    
            if (cnt1 < cnt2)
            {
            // Temporary = values[pivot]; had no effect
            // It is very likely that an IDE would have shown a warning due to static code analysis
                std::swap(values[cnt1], values[cnt2]);
                cnt1++;
                cnt2--;
            }
        }
        std::swap(values[pivot], values[cnt2]);
        myQuicksort(values, first, cnt2 - 1);
        myQuicksort(values, cnt2 + 1, last);  // <-- passing cnt2 - 1 here discarded the pivot
    } 
    

    Like the other have already suggested, to develop algorithms a debugger is really useful, because you can go through your code step by step and inspect the variables.
    Also, using an IDE with a static analyzer could help you identify the little mistakes as soon as you type them.