C Radix sort array of string

Question

First I want to thank you that you allow me to take your time. I also want to apologize for my English, it's not my first language.

I wrote a small program which sort array of strings with radix sort and counting sort. The problem is that it doesn't work properly. When length of all strings are same, then output is correct, but when string name has more than 10 characters, program gives bad answer. I found out that after increasing NAJDLUZSZY in sortPozycyjne function then everything works fine, but I don't understand why.

Here is the code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>      // na potrzeby tolower

#define DLUGOSC_NAPISU  30
#define ILOSC_NAPISOW   7
#define ZAKRES_WARTOSCI_A 128

char **A; // input array to sort
char **B; // output sorted array
char **pom;

// Sortowanie pozycyjne - tablice indeksowane od 1

void sortPrzezZliczanie(char **A, char **B, int ilosc, int pozycja) { //counting sort
    int i, j;
    int C[2048]; // pomocnicza tablica 'licznikow', ile razy wystepuje jaki znak w A

    for (i = 0; i <= ZAKRES_WARTOSCI_A; i++)
        C[i] = 0;
    for (j = 1; j <= ilosc; j++)
         C[A[j][pozycja]] += 1;
    for (i = 1; i <= ZAKRES_WARTOSCI_A; i++)
         C[i] = C[i] + C[i - 1];
    for (j = ilosc; j > 0; j--) {
        B[C[A[j][pozycja]]] = A[j];
        C[A[j][pozycja]] = C[A[j][pozycja]] - 1;
    }
}

void sortPozycyjne(char **A, char **B, int NAJDLUZSZY) {   // radix sort
    int i;
    for (i = NAJDLUZSZY; i >= 0; i--) {
        sortPrzezZliczanie(A, B, ILOSC_NAPISOW, i);
        pom = A; A = B; B = pom;     // input array to output
    }
}

void drukuj(char **tablica, int ilosc) {
    FILE *fp;

    if ((fp = fopen("output.txt", "w")) == NULL) {
        printf("Nie mogê otworzyæ pliku input.txt do zapisu!\n");
        return;
    }

    int i;
    for (i = 1; i <= ilosc; i++)
        //tablica[i]=toupper(tablica[i]);               
        fprintf(fp, "%s \n", tablica[i]);

    fclose(fp);
}

void czytaj(char **tablica, int ilosc) {
    FILE *fp;
    //int tmp;
    if ((fp = fopen("input.txt", "r")) == NULL) {
        printf("Nie mogê otworzyæ pliku output.txt do zapisu!\n");
        return;
    }

    char slowo[DLUGOSC_NAPISU];
    int i, j;
    for (i = 1; i <= ilosc; i++) {
        //fscanf (fp, "%d", &tmp);
        fscanf(fp, "%s", &slowo);
        // for (j = 0; j < strlen(slowo); j++)
        //     slowo[j] = tolower(slowo[j]); // zmniejszam wielkosc litery
        tablica[i] = (char*) malloc(sizeof(char) * DLUGOSC_NAPISU);
        strcpy(tablica[i], slowo);
    }
    fclose (fp);
}

int najdluzszyNapis(char **tablica, int ilosc) {  // finds maximum length of word
    int i, max = 0;
    for (i = 1; i <= ilosc; i++)
        if (strlen(tablica[i]) > max)
            max = strlen(tablica[i]);
    return max;
}

void taSamaDlugosc(char **tablica, int ilosc, int NAJDLUZSZY) {  
    // if string is lower than maximum then fill with nulls

    int i, j;
    for (i = 1; i <= ilosc; i++)
        for (j = 0; j <= NAJDLUZSZY; j++)
            if (!(96 < (int)tablica[i][j] && (int)tablica[i][j] < 123)) 
                tablica[i][j] = 0;
}

int main() {
    A = (char**)malloc(ILOSC_NAPISOW * sizeof(char*));
    B = (char**)malloc(ILOSC_NAPISOW * sizeof(char*));
    pom = (char**)malloc(ILOSC_NAPISOW * sizeof(char*));
    int NAJDLUZSZY; // length of the longest word

    printf("Wpisz napisy do tablicy A:\n");
    czytaj(A, ILOSC_NAPISOW);
    NAJDLUZSZY = najdluzszyNapis(A, ILOSC_NAPISOW);
    taSamaDlugosc(A, ILOSC_NAPISOW, NAJDLUZSZY);

    sortPozycyjne(A, B, NAJDLUZSZY);

    printf("\nSlownikowo posortowana tablica:\n");
    drukuj(B, ILOSC_NAPISOW);
    printf("%d", NAJDLUZSZY);
    return 0;
}

I apologize for Polish names of variables and functions. Decreasing NAJDLUZSZY also makes the answer correct.

for (j = 1; j <= ilosc; j++) --> for (j = 0; j < ilosc; j++). Maybe other issues too. — chux
– chux, Commented Nov 21, 2016 at 0:46

chqrlie · Accepted Answer · 2016-11-20 23:34:07Z

I reformatted your code to make it readable. Using proper and consistent indentation and spacing is key to clarity. Try and learn from this style.

Here are my notes:

If you are going to use Polish in your code, use it for comments, not function or variable names. The comments will help Polish reader understand the code, and the non Polish readers will still have a chance to understand the code from the variable and function names. Furthermore, it is more consistent as keywords are in English anyway. I live and work in France with French speaking programmers and we do not even comment in French anymore...
All the <= are very likely incorrect. Arrays are 0 based in C: array index values typically run from 0 to n excluded as per:
```
for (i = 0; i < size; i++) {
    ...
}
```
Casting return return value of malloc() is considered bad style. I suggest you use calloc() to allocate array initialized to all bits zero:
```
A = calloc(ILOSC_NAPISOW, sizeof(*A));
...
```
Always use {} braces for non trivial loops and tests: you have some constructions with 3 levels of unbraced statements, this is very error prone.
You should avoid global variables, especially with such names as A, B or pom.

This is as much advice as I can give in a few minutes, trying to make sense of Polish is too much of an effort, despite Radix sort being one of y favorite algorithms.

Collectives™ on Stack Overflow

C Radix sort array of string

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