• Advertisement
Sign in to follow this  

Radix sort

This topic is 3035 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi again. I'm trying to create a string sorting program which uses MSD Radix as the sorting algorithm. Here's what I've got: First the strings are read from a file, and stored into a
vector<Element>
where Element is
struct Element {
   int key;
   string data;
};
Key is the first ASCII-value of the first char in the string, for example data="car" => key = 99. Finally the elements are sorted with counting sort algorithm. And this works. However I'm only taking the first letters, so if "code" is listed before "car" it's also before "car" in the sorted vector. How should I improve my implementation? If I decide to create these so called "buckets", what would be the right datastructure for it? Recursion sounds like a good plan, but I have no idea how to implement it in this case. Thanks.

Share this post


Link to post
Share on other sites
Advertisement
I wrote an implementation of this algorithm just over a year ago. The reason you're only checking the first letter is you're probably still doing your comparisons based on the element's key property without reassigning it. Make sure if you use the key property, after the first pass, set it to the next character.
I found it easiest to simply find the longest string, create a for loop going from the longest value down to 0 and sorting it in reverse(either way sorts it properly, however reverse does it slightly faster. My professor and I never figured out why this is?). Using this, any string who's length isn't >= to counting variable's current value simply gets put into the 0 bucket, a's going in the 1 bucket, etc...
For the buckets, because you're working with words you only need a total of 27 buckets. I found the best way to do this is to declare an array of 27 vectors. Simply subtract the ascii value of 'a'+1 (the 1 offsets them so that a's go in 1 and strings too short are put into 0) from the current character you're checking and add it to the vector at that array element.

Share this post


Link to post
Share on other sites
Quote:
Original post by Scrypter
I found it easiest to simply find the longest string, create a for loop going from the longest value down to 0 and sorting it in reverse(either way sorts it properly, however reverse does it slightly faster. My professor and I never figured out why this is?). Using this, any string who's length isn't >= to counting variable's current value simply gets put into the 0 bucket, a's going in the 1 bucket, etc...


Great tip, thanks. However I'm having little trouble concatenating the strings. For example if I try to sort {"care", "cbr", "car"} it gets sorted as {"car","cbr","care"}. It happens because the strings are added in the order of their lengths, and I can't figure out how to change my implementation so they would get added in the right order.

Ideas are welcome. Here's my code:


struct Word {
int key;
std::string data;
};

void Class::sort() {
for(int length = MAX_LENGTH_; length > 0; --length) {
bool found = false;

// make new buckets for length-sized strings.
std::vector<Word> buckets_tmp[27];

// find strings with the property string.length()==length.
// wordlist is std::vector<std::string> wordlist
for(unsigned int i = 0; i < wordlist.size(); ++i) {
int word_length = wordlist.at(i).length();
if(word_length == length) {
found = true;
std::string word = wordlist.at(i);
Word tmp = {word[0],word}; // {key,data}
// add key+string to a bucket
buckets_tmp[word[0]-ASCII].push_back(tmp);
}
}

if(found) {
// go through the buckets
for(int i=0; i < 27; ++i) {
int index = 0;

// change the keys until we've reached the length of the strings
while(index!=length) {
for(unsigned int k = 0; k < buckets_tmp.size(); ++k) {
buckets_tmp[k].key=buckets_tmp[k].data[index];
}
// sort the elements with counting sort algorithm
buckets_tmp = counting_sort(buckets_tmp);
++index;
}

int limit = static_cast<int>(buckets_tmp.size())-1;
// add the strings to the final bucket in reverse
for(int k=limit;k>=0; --k) {
// buckets is std::vector<Word> buckets[27];
buckets.push_back(buckets_tmp[k]);
}
}
}
}
}


[Edited by - induction on November 1, 2009 8:35:48 AM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement