Google Answers Logo
View Question
Q: Radix Exchange Sorts that sorts strings in C++ ( No Answer,   1 Comment )
Subject: Radix Exchange Sorts that sorts strings in C++
Category: Computers > Algorithms
Asked by: empanadito-ga
List Price: $25.00
Posted: 11 May 2006 14:25 PDT
Expires: 10 Jun 2006 14:25 PDT
Question ID: 727860
I need an implementation of radix sort that works for strings in c++.
This is what I am using to generate the string randomly.

#include <iostream>
#include <cstdlib>
#define STRING_SIZE 11
#define ARRAY_SIZE 10

using std::cout;
using std::endl;

void generate(char ppt[][STRING_SIZE])
     for (int j=0; j<ARRAY_SIZE;j++)
          for(int i =0; i<STRING_SIZE-1;i++)
                  ppt[j][i] = rand()%2 + 'A';

void print(char ppt[ARRAY_SIZE][STRING_SIZE])
    for(int i=0; i<ARRAY_SIZE; i++)
  		cout << "ppt[" << i << "] = " << ppt[i] << endl;

int main()
    char array[ARRAY_SIZE][STRING_SIZE];
    return 0;
There is no answer at this time.

Subject: Re: Radix Exchange Sorts that sorts strings in C++
From: gergely-ga on 20 May 2006 23:26 PDT
The complexity of doing a radix sort on strings is that they have
arbitrary length, and an increase in length goes towards the less
significant digits. The general algorithm is:

RadixSrt(A, d)
for i <- 1 to d
   do use a stable sort to sort array A on digit i

For strings you'd have to remap the "digit" concept to be the char at
the given index. d would have to be the length of the longest string
in the set, and index 1 is the index of the last char in the longest
string, index d is always the 0th char of a string (str[0]). You'd
also have to do a check to verify that you are not accessing an
illegal index (off the end of the string): if you do, you should
assume the value of that char is 0 (since a shorter word should come
before a longer word, ex: "compute" before "computer"). Aside from
these alterations, it should run like any implementation of radix sort
for integers.

I don't have time to work out the exact code right now, but you should
be able to adjust an example that runs on integers based on the above.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  

Google Home - Answers FAQ - Terms of Service - Privacy Policy