Projeto de Algoritmos  |  Linguagem C  |  Índice  |  English

Ordenação digital

Muitos algoritmos de ordenação de vetores (como o Insertionsort, o Selectionsort, o Mergesort, o Quicksort, e o Heapsort) têm por base a comparação entre os elementos do vetor. Este capítulo trata de um algoritmo de ordenação baseado na contagem dos elementos do vetor. Esse algoritmo, por sua vez, é a mola mestra do método radix sort de ordenação de strings curtas.  (O capítulo foi adaptado da seção 5.1 do livro de Sedgewick e Wayne.)

Vetores de inteiros pequenos

Suponha que queremos rearranjar em ordem crescente um vetor v[0 . . n−1] cujos elementos são números inteiros no intervalo

0 . . R−1

sendo R é um número pequeno.  Esse intervalo é o universo do vetor.  Depois de ordenado, o vetor terá uma carreira de elementos iguais a 0, seguida de uma carreira de elementos iguais a 1, etc., e finalmente uma carreira de elementos iguais a R−1.  A figura mostra um vetor sobre o universo 0 . . 4 antes e depois da ordenação:

Exercícios 1

Ordenação por contagem

Para ordenar um vetor v[0..n-1] cujo universo é conhecido, podemos recorrer a um processo de contagem que não compara os elementos entre si. Para começar, precisamos do conceito de frequência.

A frequência de um elemento r do universo 0..R-1 é o número de ocorrências de r no vetor v[0..n-1].  Esse número será denotado por  f[r].  No vetor do exemplo acima, que tem universo 0..4, as frequências são dadas pela seguinte tabela f[0..4]:

A frequência dos predecessores de um elemento r de 0..R  é a soma f[0] + ... + f[r-1], denotada por  fp[r].  Note que acrescentamos R ao universo e que a soma que define fp[r] não inclui f[r].  É claro que fp[0] é nulo.  No vetor do exemplo acima, a frequência dos predecessores é dada pela seguinte tabela:

Observe que fp[r] é o índice a partir do qual deve começar, no vetor ordenado, a carreira de elementos iguais a r.  No exemplo acima, a carreira de 1's deve começar na posição 1, a carreira de 2's deve começar na posição 4, a carreira de 3's deve começar na posição 9, etc.

Portanto, o vetor v[0..n-1] pode ser ordenado em duas etapas:  na primeira, a tabela fp é usada para copiar os elementos de v[0..n-1] para as posições corretas de um vetor auxiliar aux[0..n-1];  na segunda, o vetor aux é copiado de volta para o espaço ocupado por v.  O seguinte código implementa o algoritmo:

// Rearranja v[0..n-1] em ordem crescente
// supondo que os elementos do vetor 
// pertencem ao universo 0..R-1.

void 
countingsort (int *v, int n, int R) 
{
   int r;
   int *fp, *aux;
   fp = malloc ((R+1) * sizeof (int));
   aux = malloc (n * sizeof (int));

   for (r = 0; r <= R; ++r) 
      fp[r] = 0;
   for (int i = 0; i < n; ++i) {
      r = v[i];
      fp[r+1] += 1; 
   }
   // agora fp[r] é a frequência de r-1
   for (r = 1; r <= R; ++r) 
      fp[r] += fp[r-1]; 
   // agora fp[r] é a freq dos predecessores
   // de r; logo, a carreira de elementos
   // iguais a r deve começar no índice fp[r]
   for (int i = 0; i < n; ++i) {
      r = v[i];
      aux[fp[r]] = v[i]; 
      fp[r]++;  // *
   }
   // aux[0..n-1] está em ordem crescente
   for (int i = 0; i < n; ++i) 
      v[i] = aux[i];

   free (fp);
   free (aux);
}

A linha * incrementa fp[r] e assim prepara o terreno para posicionar o próximo elemento do vetor que tenha valor igual a r.

Consumo de tempo.  A função countingsort consome  n + R  unidades de tempo.  Se R é pequeno (no máximo um múltiplo de n), isso é melhor que o consumo de tempo n log n de algoritmos como o Mergesort, o Quicksort, e o Heapsort.

Estabilidade.  O algoritmo que a função countingsort implementa é estável (ou seja, não altera a posição relativa de elementos de mesmo valor).  Essa propriedade é a base da aplicação da função à ordenação digital de vetores de strings a ser examinada na próxima seção.

Exercícios 2

Ordenação digital de strings de mesmo comprimento

Suponha dado um vetor v[0..n-1] de strings, todas do mesmo comprimento. (Você pode imaginar que todas as strings são ASCII, mas isso não é essencial.)  Agora considere o problema de

rearranjar o vetor em ordem lexicográfica.

No contexto desse problema, os elementos (bytes) das strings são tradicionalmente chamados dígitos, mesmo que não pertençam no conjunto 0..9.

Exemplo.  Suponha que as strings são placas de licenciamento de automóveis.  (Poderíamos nos restringir aos quarenta e três caracteres que vão de '0' a 'Z'.)  Segue um exemplo com 10 placas de 7 dígitos cada:

FON1723
EAD3312
CDA7891
FAJ4021
DOG1125
BAT7271
GIZ1234
BAT7328
BIG8733
CAT9955

(Esse exemplo é do livro de Sedgewick e Wayne.)  Para colocar esse vetor em ordem lexicográfica, podemos usar ordenação por contagem repetidas vezes:  primeiro, para ordenar pelo último dígito, depois para ordenar pelo penúltimo dígito, e assim por diante:

CDA7891  EAD3312  FAJ4021  DOG1125  CDA7891  EAD3312  BAT7271
FAJ4021  FAJ4021  DOG1125  GIZ1234  EAD3312  FAJ4021  BAT7328
BAT7271  FON1723  GIZ1234  FON1723  DOG1125  BAT7271  BIG8733
EAD3312  DOG1125  BAT7271  EAD3312  BIG8733  BAT7328  CAT9955
FON1723  BAT7328  EAD3312  FAJ4021  FAJ4021  CAT9955  CDA7891
BIG8733  BIG8733  BAT7328  BAT7271  FON1723  CDA7891  DOG1125
GIZ1234  GIZ1234  FON1723  BAT7328  BAT7271  BIG8733  EAD3312
DOG1125  CAT9955  BIG8733  CDA7891  BAT7328  GIZ1234  FAJ4021
CAT9955  BAT7271  CDA7891  BIG8733  CAT9955  DOG1125  FON1723
BAT7328  CDA7891  CAT9955  CAT9955  GIZ1234  FON1723  GIZ1234

Como a ordenação por contagem é estável, o vetor de strings acaba ficando em ordem lexicográfica.  Observe que é essencial aplicar a contagem da direita para a esquerda, ou seja, começando pelo último dígito.

Algoritmo.  O código a seguir implementa o algoritmo sugerido no exemplo.  O parâmetro W representa o comprimento comum de todas as strings (7 no exemplo acima) e o parâmetro R (menor que 256) especifica o tamanho do universo de dígitos:

typedef unsigned char byte;

// Rearranja em ordem lexicográfica um vetor v[0..n-1] 
// de strings. Cada v[i] é uma string v[i][0..W-1]
// cujos elementos pertencem ao conjunto 0..R-1.

void 
ordenacaoDigital (byte **v, int n, int W, int R) 
{
   int *fp;
   byte **aux;
   fp = malloc ((R+1) * sizeof (int));
   aux = malloc (n * sizeof (byte *));

   for (int d = W-1; d >= 0; --d) {
      int r;
      for (r = 0; r <= R; ++r) 
         fp[r] = 0;
      for (int i = 0; i < n; ++i) {
         r = v[i][d];
         fp[r+1] += 1; 
      }
      for (r = 1; r <= R; ++r) 
         fp[r] += fp[r-1]; 
      for (int i = 0; i < n; ++i) {
         r = v[i][d];
         aux[fp[r]] = v[i]; 
         fp[r]++; 
      }
      for (int i = 0; i < n; ++i) 
         v[i] = aux[i];
   }

   free (fp);
   free (aux);
}

O código ignora o byte nulo, \0, que marca o fim de cada string e portanto pode ser aplicado a qualquer vetor de vetores de bytes (desde que o valor de cada byte esteja no intervalo 0..R-1).

Esse algoritmo de ordenação é digital porque ordena as strings dígito-a-dígito.  O algoritmo também é conhecido como

• ordenação digital da direita para a esquerda,
• ordenação digital a partir do dígito menos significativo, e
• least significant digit (LSD) radix sort.

Consumo de tempo.  A função ordenacaoDigital consome  W(n+R)  unidades de tempo.  Se R é pequeno (da ordem de n na pior hipótese), o consumo de tempo é proporcional a  Wn,  ou seja, ao número total de dígitos na entrada.

Animações.  Há diversas animações do algoritmo Radixsort no YouTube. Eis uma amostra:

• 15 sorting algorithms in 6 minutes, por Timo Bingmann,
• Radix Sort on the Playground, por YoungmiSmile.

Exercícios 3