Radix sort implemented in C ++ for string

Question

I just need a C ++ radix sort implementation that works for strings

i already has one that works for normal integers

vector < vector < int> > blocks[7]; void radixSort(int rsarr[],int length){ int index; vector<int> helper; vector< vector<int> > helper2; for(int e=0;e<10;e++){ helper2.push_back(helper); } for(int r=0;r<7;r++){ blocks[r]=helper2; } for(int y=0;y<length;y++){ index=(int)(rsarr[y])%10; blocks[0][index].push_back((rsarr[y])); } for(int j=1;j<7;j++) { for(int k=0;k<10;k++) { for(int i=0;i<blocks[j-1][k].size();i++) { index=(int)(blocks[j-1][k][i]/pow(10,j))%10; blocks[j][index].push_back(blocks[j-1][k][i]); } } } int q=0; for(int f=0;f<blocks[6][0].size();f++){ rsarr[q]= blocks[6][0][f]; q++; } if(blocks[6][1].size()==1) { rsarr[q]=blocks[6][1][0]; } for(int z=0;z<7;z++) { blocks[0].clear(); } } 

Answer 1

Functions for sorting radix.

 // this is the sort function which call the radixSort Function. void Datastructure::sort() { vector<string> tempOneDimWordList; tempOneDimWordList = WordList; WordList.clear(); radixSort(tempOneDimWordList, (unsigned int)tempOneDimWordList.size(), 0); } // MSD radix function definition to sort words //lexicgraphically using most significat bits. void Datastructure::radixSort(vector<string> tempOneDimWordList, unsigned int oneDimVecSize, unsigned int offset) { if(offset == lengthOfMaxWord.length ){ return; } vector<string> towDimWordlist [MAX_LENGTH]; for (unsigned int i = 0; i < oneDimVecSize; i++){ if(offset < tempOneDimWordList[i].size()){ char c = tempOneDimWordList[i][offset]; if (c != '\0'){ towDimWordlist[(((unsigned int)c) )]. push_back(tempOneDimWordList[i]); } } else{ WordList.push_back(tempOneDimWordList[i]); } } // this loop is used to call the function recursively // to sort the words according to offset. for (unsigned int i = 0; i < (unsigned int)MAX_LENGTH; i++) { unsigned int sizeCheck = (unsigned int)towDimWordlist[i].size(); if (sizeCheck > 1){ radixSort(towDimWordlist[i], sizeCheck, offset+1); } else if(sizeCheck == 1) { WordList.push_back(towDimWordlist[i][0]); } } 

Take a look here on this blog that I wrote . There is a link to the full source code and test input files. It works great for sorting strings of arbitrary length. I had a lot of pain solving this problem. So I thought to share if he helps someone else. Happy exchange. :)

Answer 2

The problem with trying to use radix collation for strings is that strings can be arbitrarily long. Radix sorting really only makes sense for fixed-size keys.

You can still do this if you find the length of the longest string (or, as a refinement, the second longest string) as the initial pass, then iterate the radius, starting from this position.

Note that instead of saving the array for each iteration of the radius, you can use only the source and target arrays - replacing them between iterations.

Answer 3

Here is a terrible, untested combination of c and C ++ that shows one way to handle strings. There are many ways to improve it, both in clarity and in performance ...
The first thing to solve would be some way to avoid creating a large number of vectors on the stack. @Comingstorm's idea of ​​using two arrays is a good place to start.

 const int numblocks = 256; void radixSort(String rsarr[],int length, int offset = 0) { int inplace = 0; vector<String> blocks[numblocks]; //split the strings into bins for (int i=0;i<length;i++) { char c = rsarr[i][offset]; if (c!='\0') blocks[(int)c].push_back(rsarr[i]); else //put the null strings up front rsarr[inplace++]=rsarr[i]; } //for blocks all except the null terminated one, // copy back into original array in order, // then radix sort that portion of the array for (int b=1;b<256;b++) { for (int j=0;j<blocks[b].length();j++) rsarr[inplace++]=blocks[b][j]; if (j>1) radixSort(rsarr[inplace-j],j,offset+1); } }