C++ - Quicksort Algorithm for Strings Help? Running slowly?
C++ - Quicksort Algorithm for Strings Help? Running slowly? I'm writing a Quicksort algorithm that sorts an array of strings. However, I am also under the requirement that is sorts this array based on a certain set of keys, stored in another array. For example, if I had the strings:
bear, cat, yellow
I might be requested to sort them by only the 2nd and 3rd characters, so the array of keys contains:
ea, at, el
I've got the algorithm working, but for some reason, it is very slow. I was just wondering if anyone could figure out where I'm going wrong. Keep in might that list is the array of strings, keylist is the matching array of keys, left is the left index to consider while partitioning, and right is the right index in this case. Here's the code (I know the formatting is going to get messed up, try to bear with it):
void quickSort(string *keylist, string *list, int left, int right){
if(left = right){
return;
}
int lhs = left;
int rhs = right - 1;
while(lhs rhs){
while(lhs = rhs keylist[lhs] = keylist[right]){
lhs++;
}
while(rhs = lhs keylist[rhs] = keylist[right]){
rhs--;
}
if(lhs rhs){
swap(keylist[lhs], keylist[rhs]);
swap(list[lhs], list[rhs]);
}
}
swap(keylist[lhs], keylist[right]);
swap(list[lhs], list[right]);
if(lhs 0){
quickSort(keylist, list, 0, lhs-1);
}
if(lhs right - 1){
quickSort(keylist, list, lhs + 1, right);
}
}
I know it's running slowly, because it takes longer than Bubble Sort for some larger, unsorted sets of data, and this should not be happening. The swap function just swaps pointers, so it is not in that function or in the fact that two arrays are passed in, since they are by reference. Any ideas? Thanks!
|
Linear Mode
