radix sort array of strings

Question

I am trying to use radix sort to sort file contain social security and date of birth the format looks like this "###-##-####,#######.I have to apply radix sort on each fields according to command line switch. I have a radix sort that is work for int array and i am trying to modify the code for string type array but i am not sure how to accomplish this. I did a quick sort for string type by comparing strings and pivot and that is work fine however for radix sort I am not if I can do this with string type or I have to convert the string to integer. I have tried to use "atoi" to convert to integer but I am not sure how to correctly do this if I have to.

   string getMax(string arr[], int n){
    string max = arr[0];
    for (int i = 1; i < n; i++){
        if (arr[i]>max)
            max = arr[i];
    }
    return max;
   }

   void countSort(string a[], int size, int k){
    string *b = NULL; int *c = NULL;
    b = new string[size];
    c = new int[k]; 



    for (int i = 0; i <k; i++){
        c[i] = 0;
        //cout << c[i] << "\n";
    }
    for (int j = 0; j <size; j++){   
        c[(a[j]/k)%10]++;            //a[j] is a string
        //cout << c[a[j]] << endl;
    }

    for (int f = 1; f <10; f++){
        c[f] += c[f - 1];
    }

    for (int r = size - 1; r >= 0; r--){
        b[c[(a[r] / k) % 10] - 1] = a[r];
        c[(a[r] / k) % 10]--;
    }

    for (int l = 0; l < size; l++){
        a[l] = b[l];
    }

    }


    void radixSort(string b[], int r){
    string max = getMax(b, r);
    for (int digit = 1; max / digit > 0; digit *= 10){
        countSort(b, r, digit);
    }

    };

don't use raw arrays, use std::vector<std::string> or std::array<std::string, 10> if you want it with a specific size — Tony The Lion
– Tony The Lion, Commented Sep 12, 2015 at 21:04
You >don't >need the greater than signs. Proof-read before posting please. — Alan Stokes
– Alan Stokes, Commented Sep 12, 2015 at 21:24
Would it be possible to have more information (and maybe a better grammar). It is rather confusing. String: does it contain alphanumeric characters? Or is it a number in string format? @mokarab — Ely
– Ely, Commented Sep 13, 2015 at 3:58

MikeCAT · Accepted Answer · 2015-09-13 03:35:40Z

I didn't try, but I think you can do radix sort for string.

Calculate the length of the longest string in the array to sort.
Do radix sort just like for integers. Do sorting using each characters in the string. If a string is shorter than another and there is no character in the "digit", consider its value as -65536 (or a smaller value than any other characters).

UPDATE: I tested my idea and it seems working.

#include <cstdio>
#include <string>
using std::string;

size_t getMax(string arr[], int n){
    size_t max = arr[0].size();
    for (int i = 1; i < n; i++){
        if (arr[i].size()>max)
            max = arr[i].size();
    }
    return max;
}

void countSort(string a[], int size, size_t k){
    string *b = NULL; int *c = NULL;
    b = new string[size];
    c = new int[257];



    for (int i = 0; i <257; i++){
        c[i] = 0;
        //cout << c[i] << "\n";
    }
    for (int j = 0; j <size; j++){   
        c[k < a[j].size() ? (int)(unsigned char)a[j][k] + 1 : 0]++;            //a[j] is a string
        //cout << c[a[j]] << endl;
    }

    for (int f = 1; f <257; f++){
        c[f] += c[f - 1];
    }

    for (int r = size - 1; r >= 0; r--){
        b[c[k < a[r].size() ? (int)(unsigned char)a[r][k] + 1 : 0] - 1] = a[r];
        c[k < a[r].size() ? (int)(unsigned char)a[r][k] + 1 : 0]--;
    }

    for (int l = 0; l < size; l++){
        a[l] = b[l];
    }

    // avold memory leak
    delete[] b;
    delete[] c;
}


void radixSort(string b[], int r){
    size_t max = getMax(b, r);
    for (size_t digit = max; digit > 0; digit--){ // size_t is unsigned, so avoid using digit >= 0, which is always true
        countSort(b, r, digit - 1);
    }

}

int main(void) {
    string data[] = {
        "aaaba",
        "dfjasdlifjai",
        "jiifjeogiejogp",
        "aabaaaa",
        "gsgj",
        "gerph",
        "aaaaaaa",
        "htjltjlrth",
        "joasdjfisdjfdo",
        "hthe",
        "aaaaaba",
        "jrykpjl",
        "hkoptjltp",
        "aaaaaa",
        "lprrjt"
    };
    puts("before sorting:");
    for (size_t i = 0; i < sizeof(data) / sizeof(data[0]); i++) {
        printf("    %s\n", data[i].c_str());
    }
    radixSort(data, (int)(sizeof(data) / sizeof(data[0])));
    puts("after sorting:");
    for (size_t i = 0; i < sizeof(data) / sizeof(data[0]); i++) {
        printf("    %s\n", data[i].c_str());
    }
    return 0;
}

Collectives™ on Stack Overflow

radix sort array of strings

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related