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;
}
```