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.
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.