program RadixsortCar;

const MAXTAM   = 100;
      TAMCHAVE = 4;
      BASE     = 256;

type ChaveTipo    = packed array[1..TAMCHAVE] of char;
     TipoItem     = record 
                      Chave: ChaveTipo;
                      { outros componentes }
                    end;
     TipoIndice   = 0..MAXTAM;
     TipoVetor    = array [TipoIndice] of TipoItem;
     TipoContador = array[0..BASE-1] of integer;

var A: TipoVetor;
    B: TipoVetor;    { Vetor auxiliar usado dentro do procedimento Contagem }
    C: TipoContador; { Arranjo auxiliar usado dentro do procedimento Contagem }
    i: TipoIndice;
    n: TipoIndice;
 
procedure ContagemCar (var A   : TipoVetor; 
                       n       : TipoIndice;
		       var NCar: integer);
var i, j: integer;
begin
  for i := 0 to BASE - 1 do C[i] := 0;
  for i := 1 to n do begin j:=ord(A[i].Chave[NCar]); C[j]:=C[j]+1; end;
  for i := 1 to BASE - 1 do C[i] := C[i]+C[i-1];
  for i := n downto 1 do
    begin
    j := ord (A[i].Chave[NCar]);
    B[C[j]] := A[i];
    C[j] := C[j] - 1;
    end;
  for i := 1 to n do A[i] := B[i];
end; { ContagemCar }

procedure RadixsortCar (var A: TipoVetor; n: TipoIndice); 
var 
  i, NCar: integer; 
begin
  for i := TAMCHAVE downto 1 do 
    begin
    NCar := i;
    ContagemCar (A, n, NCar);
    end;
end; { RadixsortCar }

procedure Imprime (var V: TipoVetor; n: TipoIndice);
begin
  for i := 1 to n do write (V[i].Chave,' ');
  writeln;
end;

procedure Testa (var V: TipoVetor; n: TipoIndice);
begin
  for i := 2 to n do
    begin
    if V[i].Chave < V[i-1].Chave
    then begin
         write ('ERRO: ');
         Imprime (V, n);
         halt;
         return;
         end;
    end;
  write ('OK: ');
  Imprime (V, n);
end;

begin
  n:=3;
  a[1].Chave[1]:= 'c'; a[1].Chave[2]:= 'c'; a[1].Chave[3]:= 'c'; 
  a[2].Chave[1]:= 'b'; a[2].Chave[2]:= 'b'; a[2].Chave[3]:= 'b'; 
  a[3].Chave[1]:= 'x'; a[3].Chave[2]:= 'x'; a[3].Chave[3]:= 'x'; 
 
  write ('Desordenado : ');
  Imprime (A, n);

  write ('Radixsort  ');
  RadixsortCar (A, n);
  Testa (A, n);
end.