[Curso de AeED - Aula 07] [Algoritmo] Ordenação - digital

Este capítulo trata de um algoritmo de ordenação que é muito rápido quando os números a ordenar são todos pequenos.  Esse algoritmo, por sua vez, é a mola mestra de um algoritmo muito rápido de ordenação de strings curtas.

O capítulo foi adaptada 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 (quando comparado com n).  Esse intervalo é, portanto, o universo dos elementos do vetor.  Exemplo:  A figura mostra um vetor com universo 0..4 antes e depois da ordenação:

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
2	3	3	4	1	3	0	3	1	2	2	1	2	4	3	4	4	2	3	4

0

1

1

1

2

2

2

2

2

3

3

3

3

3

3

4

4

4

4

4

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.

Poderíamos ordenar o vetor usando um dos algoritmos baseados em comparações, como o de inserção, o Mergesort, o Quicksort, ou o Heapsort.  Mas podemos fazer algo mais rápido se R for pequeno.

Exercícios 1

1. Vetor de bits.  Escreva uma função que rearranje em ordem crescente um vetor v[0..n-1] cujos elementos são 0s e 1s. 
2. DNA.  Escreva uma função que rearranje em ordem crescente um vetor cujos elementos são os caracteres A, C, G e T do código genético.  Comece por transformar o conjunto  A C G T  no intervalo numérico 0..3.

Ordenação por contagem

A frequência de um elemento r do universo 0..R-1 em um vetor v[0..n-1] é o número de ocorrências de r no vetor.  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]:

	0	1	2	3	4
f	1	3	5	6	5

A frequência dos predecessores de um elemento r de 0..R-1 é a soma f[0] + ... + f[r-1], denotada por fp[r]  (note que a soma não inclui f[r]).  É claro que fp[0] é nulo, e é natural definir fp[R] como f[0] + ... + f[R-1].  No vetor do exemplo acima, a frequência dos predecessores é dada pela seguinte tabela fp[0..5]:

	0	1	2	3	4	5
fp	0	1	4	9	15	20

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.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
0	1	1	1	2	2	2	2	2	3	3	3	3	3	3	4	4	4	4	4

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

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
0	1	1	1	2	2	2	2	2	3	3	3	3	3	3	4	4	4	4	4

O seguinte código implementa as duas etapas do 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;

fp = malloc ((R+1) * sizeof (int));
int *fp, *aux;

aux = malloc (n * sizeof (int));
for (r = 0; r <= R; ++r) 
      fp[r] = 0;

fp[r + 1] += 1; 
for (int i = 0; i < n; ++i) {
      r = v[i];
   }

// agora fp[r] é a frequência de r-1

for (r = 1; r <= R; ++r) 
fp[r] += fp[r-1]; 

// 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];

fp[r]++;  // *
aux[fp[r]] = v[i]; 

}

// 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 * prepara o terreno para 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 (apenas uma fração 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.  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

1. Critique a seguinte versão simplificada da função countingsort:

   
      int *f = malloc (R * sizeof (int)); 
   
   
   for (int r = 0; r < R; ++r)  f[r] = 0;
   
   for (int i = 0; i < n; ++i)  f[v[i]] += 1; 
   int i = 0;
   
   for (int k = 0; k < f[r]; ++k)  // 7
   for (int r = 0; r < R; ++r)        // 6
   
   free (f);
   
   v[i++] = r;                  // 8
   

   [Solução]
2. Vetor de structs.  Imagine que o vetor v[0..n-1] representa o cadastro de funcionários de uma empresa.  Cada elemento do vetor é uma struct com dois campos: um campo num, que dá o número do funcionário, e um campo nome, que dá nome do funcionário.  Suponha que cada número de funcionário é um inteiro com três dígitos decimais.  Adapte o código de countingsort para ordenar v[0..n-1] pelo campo num.
3. Vetores de letras.  Adapte a função countingsort para ordenar um vetor cujos elementos pertencem ao conjunto de caracteres A..Z.
4. Mostre que a função countingsort é estável.

Ordenação digital de strings de mesmo comprimento

Suponha dado um vetor v[0..n-1] de strings de mesmo comprimento e 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 estejam todos no conjunto 0..9.

Exemplo: Suponha que as strings são placas de licenciamento de automóveis, e portanto usam apenas os 128 caracteres do alfabeto ASCII.  (Poderíamos nos restringir aos 43 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



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.  Como a ordenação por contagem é estável, o vetor acaba ficando em ordem lexicográfica: 

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

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 especifica o tamanho do universo de dígitos (128, no exemplo acima): 

// 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 pertence ao conjunto 0..R-1.


void 

ordenacaoDigital (char **v, int n, int W, int R) 
{
   int *fp;
   char **aux;

fp = malloc ((R+1) * sizeof (int));
aux = malloc (n * sizeof (char *));


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

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

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

}
for (int i = 0; i < n; ++i) 
         v[i] = aux[i];
   }

   free (fp);

free (aux);

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,
• LSD (least significant digit) radix sort.

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

Exercícios 3

1. Na função ordenacaoDigital, diga o que acontece se trocarmos a linha  for (d = W-1; d >= 0; --d)  por  for (d = 0; d < W; ++d).
2. [Sedgewick-Wayne 5.1.2]  Aplique o algoritmo de ordenação digital ao vetor de strings

   no is th ti fo al go pe to co to th ai of th pa
   

3. [Sedgewick-Wayne 5.1.9]  Escreva uma versão de ordenacaoDigital para vetores de strings de comprimento variável.
4. [Sedgewick-Wayne 5.1.20]  Escreva uma função que receba inteiros n e W e produza um vetor de n strings aleatórias com W caracteres ASCII cada.
5. Experimento: Compare experimentalmente o desempenho das funções ordenacaoDigital e heapsort.  Para fazer a comparação, gere vetores aleatórios com n strings, cada string com W dígitos decimais.  Faça testes para n igual a 1 mil, 2 mil, 4 mil, 8 mil, … , 512 mil e W igual a 1, 2, 4, 8.
6. [Sedgewick 10.36]  Implemente o algoritmo de ordenação digital para listas encadeadas.

---

Radix sort on the playground: YouTube vídeo.

---

Atualizado em 2017-06-07

http://www.ime.usp.br/~pf/algoritmos/

Paulo Feofiloff

DCC-IME-USP