arrayscc-stringsradix-sort

LSD Radix for a fixed count array


I would like to create a radix LSD to sort strings. I tried to adapt to a count[27] instead of count[256], because the exercise requires it. I must use A[I][d] - 'a' + 1 for [a-z] and 0 for spaces, but it is not sorting correctly. Some strings on my tests have been duplicated. How can I solve this?

#define MAX 15
void foo(char** A, int n, int k, int max) {
  int i, d;
  char** B = (char**)malloc(sizeof(char*) * n);

  for(i = 0; i < n; i++)
    B[i] = (char*)malloc(sizeof(char) * max);

  for (d = max - 1; d >= 0; d--) {
    int* count = (int*)malloc(sizeof(int) * k);
    
    for(i = 0; i < k; i++)
      count[i] = 0;

    for (i = 0; i < n; i++) {
      if(A[i][d] == 32) count[0]++;
      else count[A[i][d] - 'a' + 1]++;
    }

    for (i = 1; i < k; i++)
      count[i] += count[i - 1];
    
    for (i = n - 1; i >= 0; i--) {
      if(A[i][d] == 32) {
        strcpy(B[count[0] - 1], A[i]);
        count[0]--;
      }
      else {
        strcpy(B[count[A[i][d] - 'a' + 1] - 1], A[i]);
        count[A[i][d]]--;
     }
    }

    for (i = 0; i < n; i++)
      strcpy(A[i], B[i]);

    free(count);
  }

  for(i = 0; i < n; i++) free(B[i]);
  free(B);
}

Solution

  • There are lots of stylistic and efficiency issues with the program, but I found only three actual errors:

    1. You rely on the values of all the elements of each A[i], but you do not reliably set all of them. Specifically, malloc() does not initialize the memory it allocates, and scanf() does not write any bytes past the string terminator. You could fix this by allocating via calloc() instead of malloc().

    2. You do not allocate enough space for your strings in the first place. You rely on there being space for MAX characters plus a string terminator, but you allocate space only for MAX characters.

    3. (Likely the issue responsible for the observed misbehavior) your sort function does not manage its count array correctly. Specifically, this is wrong:

              count[A[i][d]]--;
      

      It should be

              count[A[i][d] - 'a' + 1]--;