Radix sort implemented in c++ for string [closed]

问题:

i just need radix sort implementation in c++ language which works for strings

i already have the one which 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();
    }
}

回答1:

Functions for radix sort.

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

Have a look here in this blog that I have written. Download link of the full source code and test input files are available there. It works really fine for sorting strings of arbitrary length. I had lots of pain while solving this problem. So thought to share if it helps someone else. Happy sharing. :)

回答2:

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

You can still do it if, as an initial pass, you find the length of the longest string (or, as a refinement, the second-longest string), then do radix iterations starting at that position.

Note that, rather than saving an array per radix iteration, you can use only a source and destination array -- swapping them between iterations.

回答3:

Here is a horrible, untested mix of c and c++ which shows one way to handle strings. There are many ways to improve it, both in clarity and performance...
The first thing to tackle would be some way of avoiding creating a huge number of vectors on the stack. @comingstorm's idea about 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);
  }
}