#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

#define MAXTAM 10000000  /* Numero maximo de elementos a ordenar */
#define TAMCHAVE 4  /* Tamanho real da string: TAMCHAVE -1 */
#define BASE 256

typedef char TipoChave[TAMCHAVE];
typedef int TipoIndice;

typedef struct TipoItem {
  TipoChave Chave;
} TipoItem;

typedef TipoItem TipoVetor[MAXTAM + 1];

TipoVetor A;
TipoVetor B;
int C[BASE];

void ContagemCar(TipoItem *A, TipoIndice n, int k)
{ int i, j;
  for ( i = 0; i <= BASE - 1; i++) C[i] = 0;
  for ( i = 1; i <= n; i++)
    { j = (int) A[i].Chave[k];
      C[j] = C[j] + 1; 
    }
  if (C[0] == n) return;
  for (i = 1; i <= BASE - 1; i++) C[i] = C[i] + C[i-1];
  for (i = n; i > 0; i--)
    { j = (int) A[i].Chave[k];
      B[C[j]] = A[i];
      C[j] = C[j] - 1;
    }
  for (i = 1; i <= n; i++) A[i] = B[i];
}

void RadixsortCar(TipoItem *A, TipoIndice n)
{ int i;
  for (i = TAMCHAVE - 1; i >= 0; i--) ContagemCar (A, n, i);
}

void Imprime(TipoItem *V, TipoIndice n)
{ int i;
  for (i = 1; i <= n; i++)
    printf("%s ", V[i].Chave);
  printf("\n");
}

void Testa(TipoItem *V, TipoIndice n)
{ int i;
  for (i = 2; i <= n; i++)
  { if (strcmp(V[i].Chave, V[i-1].Chave) < 0)
    { printf("ERRO\n");
      return;
    }
  }
  printf("OK: ");
  Imprime(V, n);
}

int main(int argc, char **argv)
{ int n = 10;  
  int i, j;
  int TamString = TAMCHAVE - 1; 
  for (i = 1; i <= n; i++)
    for (j = 0; j < TamString; j++) A[i].Chave[j] = 'a' + (rand() % 26);
  A[i].Chave[TamString] = 0;
  printf ("Desordenado: ");
  Imprime(A, n);
  printf ("RadixsortCar ");
  RadixsortCar(A, n);
  Testa (A, n);
  return 0;
}