I am attempting to write a Quicksort algorithm and my partition function is not behaving correctly.
here is the code
int CDataAnalyzerDlg::partition1(int first, int last)
{
int pivot = myVector[((first + last) / 2)];
int left = first;
int right = last;
swap(myVector[left], myVector[right]);
while (left < right)
{
while (pivot < myVector[right])
right--;
while (left < right && (myVector[left] < pivot || myVector[left] == pivot))
left++;
if (left < right)
swap(myVector[left], myVector[right]);
}
int pos = right;
myVector[first] = myVector[pos];
myVector[pos] = pivot;
return pos;
}
void CDataAnalyzerDlg::Quicksort(int first, int last)
{
int location;
if(first < last)
{
location = partition1(first, last);
Quicksort(first, location - 1);
Quicksort(location + 1,last);
}
when this runs the elements in my vector are duplicated at several points and
as I continue to run it they duplicate even more (although the number of elements remains the same). I'm using Microsoft Visual Studio .Net 2003