• ### What is your GameDev Story?

Public Group

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

## 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 on other sites
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 on other sites
Quote:
 Original post by ScrypterI 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]

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 15
• 14
• 46
• 22
• 27
• ### Forum Statistics

• Total Topics
634053
• Total Posts
3015264
×