C++ - Quicksort Algorithm for Strings Help?

David · #1 02-18-2010, 07:04 PM

C++ - Quicksort Algorithm for Strings Help?

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

Thanks!

Chris C · #2 02-18-2010, 07:04 PM

Well, as a suggestion if this isn't for class only.
Why don't you simply use the existing qsort() function?
http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/

Define 2 different compare() functions.
Kind of like this:
int compareKeys (const void * a, const void * b);
int compareStrings (const void * a, const void * b);

juliepelletier · #3 02-18-2010, 07:05 PM

First of all, your need to use the two lists doubles the work. I would try creating a struct for each record in list to include an id which could link back the string to keylist.

Of course you need to make sure you only swap pointers, not the contents, as this would be extremely heavy.

You could also use the built-in qsort which already takes a custom comparison function. You would basically just need to provide that function access to the keylist, either as a global or static (at the file level) variable.

Otherwise the code looks OK.

Pete S · #4 02-18-2010, 07:05 PM

Code looks fine to me, how did you implement swap?

Are you swapping pointers or values in swap? Excessive copying in swap may be your speed problem.

MichaelInScarborough · #5 02-18-2010, 07:07 PM

I agree with Cris. You could use the qsort function in order to determine, whether your algorithm is comparibly slow. If it is, then you can start analyzing, where things go south!
this could be your comparison function

int compare(const void *a, const void *b)
{
string *strA = (string *)a, *strB = (string *)b;
return strA-compare(*strB);
}

In case you hate pointers you could try something like this:
int compare(const void *a, const void *b)
{
string strA = *(string *)a, strB = *(string *)b;
return strA.compare(strB);
}