Debugging Quicksort Algorithm

[nathan.pavlovsky]

Hello Programmers!

I am trying to write a recursive implementation of the quicksort algorithm in C++.

I believe you all know what it is so I shall not go into the details.

However, I run this, but it never ends. Going through it with a debugger shows that my partitioning method works... and with my base case being for the "left" and "right" indexes being equal to each other or out of valid range, so my thoughts are that the recursion should stop when needed.

Please take a look at this below, if you have time, and if you see the reason why my algorithm does not work correctly, please let me know.

The partitioning function works properly... I have checked it multiple times, so I do not understand why the whole program does not work.

Thanks so much!

My work is below.

    //  Implementation of the quicksort algorithm

    #include <iostream>
    #include <array>
    using namespace std;

    //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

    template<size_t size>
    int partition(array<int,size>& toPartition,unsigned start,unsigned end)   //start and end are indexes in the array
    {
        //returns the final location of the pivot point
        unsigned pivot=start;
        unsigned left=start;
        unsigned right=end;

        unsigned counter=0;
        while (left < right)
        {
            if (counter%2 == 0)
            {
                //find a number that is less than pivot on the right, if possible
                while (toPartition[pivot] <= toPartition[right] && right > pivot)
                {
                    --right;
                }

                if (right > pivot && toPartition[pivot] > toPartition[right])
                {
                    //found a number in the right subarray that is less than the pivot....
                    swap(toPartition[pivot],toPartition[right]);

                    //swap indexes of pivot and right
                    pivot=right;
                    --right;

                    ++left; //the item in index left is now in place... so continue on.
                }
            }

            else
            {
                while (left < pivot && toPartition[pivot] >= toPartition[left] )
                {
                    ++left;
                }

                if (left < pivot && toPartition[pivot] < toPartition[left])
                {
                    swap(toPartition[pivot],toPartition[left]);

                    //swap indexes of pivot and left
                    right=pivot-1;
                    pivot=left;
                    ++left;
                }
            }

            //increment counter to shift sides examined
            ++counter;
        }

        return pivot;


}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

template<size_t size>
void recurQuickSort(array<int,size>& toSort,unsigned start,unsigned end)
{
    if (start == end)
        //this is the base case for recursion as the subarray contains one element and thus, is "sorted"
        return;

    else if (start < 0 || end >= toSort.size())
        //exceeding the proper limits of the array with invalid indexes
        return;

    else
    {
        //the array is not sorted... start sorting
        unsigned pivot=partition(toSort,start,end);
        recurQuickSort(toSort, start, pivot-1);    //lower subarray
        recurQuickSort(toSort, pivot+1, end);      //upper subarray
    }
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

template<size_t size>
void quickSort(array<int,size>& toSort)
{
    recurQuickSort(toSort, 0, toSort.size()-1);
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main()

//DEBUG WHY THIS DOES NOT WORK!!
{
    array<int, 10> toSort = {37,2,6,4,89,8,10,12,68,45};
    cout << "Before sorting, toSort is: ";
    copy(toSort.cbegin(),toSort.cend(),ostream_iterator<int>(cout," "));
    cout << endl;
    quickSort(toSort);

    cout << "\n\nAfter sorting, toSort is: ";
    copy(toSort.cbegin(),toSort.cend(),ostream_iterator<int>(cout," "));
    cout << endl;

}

[rubberman]

Have you really analyzed the original qsort algorithm? Read Knuth's volume 3, Sorting and Searching? If you haven't adsorbed that, then you don't know what the fark you are doing!

[nathan.pavlovsky]

I have studied it via online videos and via C++ How to Program (which gave me the exercise). I understand that in the original algorithm, the original pivot is in the middle of the array, but I was told to take the first term as the original pivot and treat it as such.

I do not have Knuth's book... maybe you can tell me what it says about what I am doing?

[nathan.pavlovsky]

Further examination of the algorithm with printouts revealed what went wrong... the start and the end values for the recurQuickSort function would sometimes be wrong relative to each other... with start > end... adding a '>' into the first 'if' structure fixed this.

I am sharing this for the benefit of those that will read this at a later time.

The correct function code is below... and the rest was not altered

template<size_t size>
void recurQuickSort(array<int,size>& toSort,unsigned start,unsigned end)
{

     //base case for recursion as the subarray contains one element (or the indexes are wrong relative to each other) and thus, is "sorted"
    if (start >= end)   //NOTE THE >= !!
    {
        return;
    }
    else if (start < 0 || end >= toSort.size())
    {
        //another base case for recursion: exceeding the proper limits of the array with invalid indexes
        return;
    }

    else
    {
        //the array is not sorted... start sorting
        unsigned pivot=partition(toSort,start,end);
        recurQuickSort(toSort, start, pivot-1);    //lower subarray
        recurQuickSort(toSort, pivot+1, end);      //upper subarray
    }
}