Least significant digit (LSD) radix sort of strings

Question

I am learning string algorithms and wrote this C example based on a Java example I found online. Any feedback relating to style, code clarity, whether it is generic enough to be re-used, interface, etc, etc would be very much appreciated.

/*
 Demonstration of least significant digit (LSD) radix sort of strings
 Specifically UK vehicle registration numbers
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define PLATELENGTH 7
#define ALPHABET 36

/* Characters must be uppercase or digits */
void lsd_string_sort(char* a[], const int length, int string_size) {
   int R = ALPHABET;
   int W = string_size;
   const int N = length;
   char id = 0;
   char** aux = (char**)malloc(length * string_size);

   for(int d = W-1; d >= 0; d--) {
      int* count = (int*)calloc(R+1, sizeof(int));
      /* whether character or digit */
      id = (*(a[0]+d) >= '0' && *(a[0]+d) <= '9') ? '0' : 'A';
      /* Compute frequency counts */
      for(int i = 0; i < N; i++)
         count[*(a[i]+d) - id + 1]++;
      /* transform counts to indices */
      for(int r = 0; r < R; r++)
         count[r+1] += count[r];
      /* distribute to temp array */
      for(int i = 0; i < N; i++) 
          aux[count[(*(a[i]+d) - id)]++] = a[i];
      /* copy back to original array */
      for(int i = 0; i < N; i++)
         a[i] = aux[i];

      free(count);
   }
   free(aux);
}


int main() {

   /* in real application would use re-sizing array */
   char* plates[1000] = {0};

   int arr[10] = {0};
   char plate[16];  /* extra space just in case */
   int n = 0;
   printf("Please enter list of UK registration plates (skip spaces between registration numbers)\n");
   while(scanf("%s", &plate) == 1) {
      plates[n++] = strdup(plate); 
   }

   printf("List before sorting\n");
   for(int i = 0; i < n; i++)
      printf("%s\n", plates[i]);

   lsd_string_sort(&plates[0], n, PLATELENGTH);

   printf("List after sorting\n");
   for(int i = 0; i < n; i++)
      printf("%s\n", plates[i]);

   while(n > 0)
      free(plates[--n]);

   return 0;
}

Answer 1

1. You can run into a buffer overflow when the user types in more than 15 characters. You should use scanf("%15s", &plate); - Note that scanf will automatically add the null terminator (hence 15 instead of 16).

2. While it is accepted to use single letter variables for loops you have abused this extensively in your sorting routine.

   • What is a, what is length, what is string_size? Just from reading the method (without reading main) it's very hard to figure out what the individual parameters are supposed to mean.

   • Why is length const but string_size isn't?

   • Why are you copying the parameters and ALPHABET into local variables which have short meaningless names?

All in all the code is fairly clean, but you should de-obfuscate it a bit.

Answer 2

• This macro name is misleading:

  #define ALPHABET 36
  

  The alphabet consists of 26 letters, not 36. But in a CS context, this can be implied (in this case, it appears to include A-Z and 0-9).

  However, this macro is storing the alphabet's size, not the alphabet itself. The name should clearly specify that. A more appropriate name could be ALPHABET_LENGTH.

  On another note, the other macro should be renamed to PLATE_LENGTH. Underscores are commonly used to separate each word in a macro.

• Avoid single-character variable names:

  int R = ALPHABET;
  int W = string_size;
  

  Based on the context (fortunately), I can tell that these hold sizes. Other than that, they are very unclear and could lead to maintenance problems at some point. Always give variables descriptive names, unless they're simple loop counters.

• You have the list-displaying code in main() twice. Why not make it a function? This will reduce the amount of code in main() and maintain DRY, making it clearer to read and to maintain.

  void display(char list[], int n)
  {
      for (int i = 0; i < n; i++)
          printf("%s\n", plates[i]);
  }
  

  You could keep the label outputs in main(), right before the function calls.

Answer 3

I few items that I didn't see mentioned yet:

• You have an unused variable named arr.

• Your format specifies the type char *, but your argument has type char (*)[16]

  while(scanf("%s", &plate) == 1) {
  

  To fix it, remove the &.

• All you do in this loop is print a string, with no formatting.

  for(int i = 0; i < n; i++)
      printf("%s\n", plates[i]);
  

  Use puts() when you are only printing the string and not formatting it. As a bonus, you don't have to remember the newline (\n) character.

  for(int i = 0; i < n; i++) puts(plates[i]);
  

• I am led to believe that you might be compiling your code as c++ code.

  char** aux = (char**)malloc(length * string_size);
  

  Yes, it might be valid, but that line right there would be unacceptable when compiling as C code. You shouldn't be doing that.

  Here is a very long list of the incompatibilities between ISO C and ISO C++. Those are the reasons you compile C code, as C code.

  If I happen to be wrong in my assumption that you are compiling C code as C++ code, you still should not be casting the results of malloc().

Answer 4

Your code would be a lot easier to understand if you renamed your variables. Don't do this just for others. Do it for yourself. If you look at this code a few months later, I bet you yourself will have trouble reading it. Rename the variables until the logic just flows. When the comments become pointless, you have succeeded (and then can drop the comments too).

---

In addition to what others already pointed out, I would just point out some things you could simplify.

Instead of these pointer arithmetics:

id = (*(a[0]+d) >= '0' && *(a[0]+d) <= '9') ? '0' : 'A';
count[*(a[i]+d) - id + 1]++;
aux[count[(*(a[i]+d) - id)]++] = a[i];
lsd_string_sort(&plates[0], n, PLATELENGTH);

You could write more intuitively:

id = a[0][d] >= '0' && a[0][d] <= '9' ? '0' : 'A';
count[a[i][d] - id + 1]++;
aux[count[(a[i][d] - id)]++] = a[i];
lsd_string_sort(plates, n, PLATELENGTH);

---

These initializations are pointless in your code:

char* plates[1000] = {0};
int arr[10] = {0};

since you only access the elements of plates that you have assigned, always, from index 0 to n. And you never use arr. There are many practical cases when you have to initialize arrays to 0, but this is not one of them.