UPDATE
Brilliant comments. Here is a cleaned up version.
/*
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 PLATE_LENGTH 7 /* UK number plates have 7 alphanumeric chars, space removed */
#define ALPHABET_SIZE 36 /* A-Z, 0-9 */
/* Characters must be uppercase or digits */
void lsd_string_sort(char* array[], const int size, const int width, const int radix) {
char id = 0;
char** aux = malloc(size * width);
int d, i, r;
int* count;
for(d = width-1; d >= 0; d--) {
count = calloc(radix+1, sizeof(int));
/* whether character or digit */
id = array[0][d] >= '0' && array[0][d] <= '9' ? '0' : 'A';
/* Compute frequency counts */
for(i = 0; i < size; i++)
count[array[i][d] - id + 1]++;
/* transform counts to indices */
for(r = 0; r < radix; r++)
count[r+1] += count[r];
/* distribute to temp array */
for(i = 0; i < size; i++)
aux[count[(array[i][d] - id)]++] = array[i];
/* copy back to original array */
for(i = 0; i < size; i++)
array[i] = aux[i];
free(count);
}
free(aux);
}
void print_list(char* list[], int n)
{
int i;
for (i = 0; i < n; i++)
puts(list[i]);
}
int main() {
/* in real application would use re-sizing array */
char* plates[1000];
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("%7s", plate) == 1) {
plates[n++] = _strdup(plate);
}
printf("List before sorting\n");
print_list(plates, n);
lsd_string_sort(plates, n, PLATE_LENGTH, ALPHABET_SIZE);
printf("List after sorting\n");
print_list(plates, n);
while(n > 0)
free(plates[--n]);
return 0;
}
