Hi everyone. I've been struggling with a quicksort implementation here. I think - scratch that - I know i'm overrunning an array (erm, vector) based on how it explodes, but I honestly can't see it and I have no debugger. I slept on it but fresh eyes didn't get me anywhere. I've been digging around online for a while but there are a thousand different ways to do quicksort and it just ends up being confusing to keep it all straight.
Oh and two things to note:
-Yes, I have to use vectors. I've no idea why.
-There are global variables (don't shoot me) being incremented for performance tracking and comparing sorts.
Here's the mess:
//Quick Sort
vector<int> quickSort(vector<int> &data, int left, int right){
if(left>=right){ return data; }
else{
int split = partition(data, left, right);
recurses+=2;
quickSort(data, left, split-1);
quickSort(data, split+1, right);
}
}
//Quick sort partitioning
int partition(vector<int> &data, int left, int right){
int pivot=left;
int i=left+1;
int j=right;
while (i<j){
for(;i<right && (data[i]<=data[pivot]);i++) { compares++; }
for(;(data[j]>data[pivot]);j--) { compares++; }
if(i<j){
swap(data[i],data[j]);
swaps++;
}
}
swap(data[pivot], data[j]);
swaps++;
return j;
}
I feel like i'm somehow passing bad indeces to the partition function and the for loops are running away. Every once in a while the function will finish (it's fed 1-10 in random order) but the first and second elements of the vector are always garbage when it does. Mind you, it's certainly possible that I have more than one error going on.
Thoughts?