Aula 25 - Ordenação de Strings: Counting Sort e Radix Sort
Todos os algoritmos de ordenação estudados até agora — Merge Sort, Quick Sort, Heap Sort — baseiam-se em comparações entre elementos (“a[i] < a[j]?”). Algoritmos desse tipo não conseguem ser mais rápidos que O(n log n) no pior caso (n = número de elementos a ordenar). Mas e se as chaves não forem arbitrárias — e se forem inteiros em um intervalo conhecido, ou strings sobre um alfabeto fixo? Nesses casos podemos ordenar mais rápido que O(n log n) usando algoritmos que exploram a estrutura das chaves, sem comparar elementos.
Nesta aula estudamos dois algoritmos não baseados em comparações: Counting Sort e Radix Sort. Ambos são estáveis e atingem complexidade O(n) em condições adequadas.
1. Counting Sort
1.1 Ideia
Dado um vetor de n inteiros no intervalo [0, k] (k = maior valor possível de uma chave), contamos quantas vezes cada valor aparece, depois usamos essas contagens para posicionar cada elemento diretamente em sua posição correta. Nenhuma comparação entre elementos é realizada.
| Analogia: um professor quer empilhar as provas por nota (0 a 10). Em vez de comparar provas duas a duas, ele conta quantas provas têm cada nota. Se há 3 provas com nota 0 e 5 com nota 1, já sabe que as provas de nota 2 começam na 9ª posição da pilha. É exatamente isso que o Counting Sort faz. |
| Pré-requisito: os valores devem ser inteiros (ou mapeáveis a inteiros) em um intervalo [0, k] conhecido antecipadamente. O algoritmo aloca um vetor auxiliar de tamanho k+1; portanto, k deve ser pequeno o suficiente para caber na memória. |
1.2 Algoritmo passo a passo com exemplo
Entrada: [4, 1, 3, 1, 2, 4, 1, 3, 2, 4, 1] — n=11, k=4
Cada valor tem uma cor. As letrinhas (1a, 1b, ...) não fazem parte da chave: servem só para acompanharmos qual “1” é qual e verificarmos a estabilidade no final.
| a[] | 4a | 1a | 3a | 1b | 2a | 4b | 1c | 3b | 2b | 4c | 1d |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Passo 1 — Contar: count[v] = número de vezes que v aparece na entrada.
| v | 0 | 1 | 2 | 3 | 4 |
| count[v] | 0 | 4 | 2 | 2 | 3 |
| contagem | – | ■■■■ | ■■ | ■■ | ■■■ |
Passo 2 — Prefixo acumulado: count[v] passa a ser o número de elementos ≤ v (soma cumulativa).
| v | 0 | 1 | 2 | 3 | 4 |
| conta | 0 | 0+4 | 4+2 | 6+2 | 8+3 |
| count[v] | 0 | 4 | 6 | 8 | 11 |
Interpretação: count[v] indica onde termina a faixa do valor v no vetor de saída (output[]) (índice base 1 da última posição). Por exemplo, count[2] = 6: existem 6 elementos ≤ 2, então o último 2 vai para a posição 5. Ou seja, a saída já fica “reservada” por faixas:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| output[] | |||||||||||
| faixa do 1 | faixa do 2 | faixa do 3 | faixa do 4 | ||||||||
Passo 3 — Posicionar (percorrendo a entrada da direita para a esquerda para garantir estabilidade):
Para cada a[i] (i de n-1 até 0):
output[ count[a[i]] - 1 ] = a[i]
count[a[i]]--
Acompanhe a saída sendo preenchida (a célula com borda vermelha é a que acabou de ser colocada):
| i | a[i] | posição | count após | saída após o passo | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 10 | 1d | output[4−1] = output[3] | count[1] = 3 |
| |||||||||||
| 9 | 4c | output[11−1] = output[10] | count[4] = 10 |
| |||||||||||
| 8 | 2b | output[6−1] = output[5] | count[2] = 5 |
| |||||||||||
| 7 | 3b | output[8−1] = output[7] | count[3] = 7 |
| |||||||||||
| 6 | 1c | output[3−1] = output[2] | count[1] = 2 |
| |||||||||||
| 5 | 4b | output[10−1] = output[9] | count[4] = 9 |
| |||||||||||
| 4 | 2a | output[5−1] = output[4] | count[2] = 4 |
| |||||||||||
| 3 | 1b | output[2−1] = output[1] | count[1] = 1 |
| |||||||||||
| 2 | 3a | output[7−1] = output[6] | count[3] = 6 |
| |||||||||||
| 1 | 1a | output[1−1] = output[0] | count[1] = 0 |
| |||||||||||
| 0 | 4a | output[9−1] = output[8] | count[4] = 8 |
|
Saída:
| output[] | 1a | 1b | 1c | 1d | 2a | 2b | 3a | 3b | 4a | 4b | 4c |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Note que os “1” aparecem na saída na mesma ordem em que estavam na entrada: 1a, 1b, 1c, 1d. O mesmo vale para os 2, 3 e 4.
Por que percorrer da direita para a esquerda? Para garantir estabilidade: elementos com chaves iguais aparecem na saída na mesma ordem relativa em que apareciam na entrada. Como count[v] aponta para o fim da faixa de v, o primeiro v encontrado (o mais à direita na entrada) vai para o fim da faixa. Isso é crítico quando Counting Sort é usado como sub-rotina do Radix Sort.
|
1.3 Estabilidade na prática
Uma turma já está em ordem alfabética e queremos agrupá-la por conceito (A, B, C — apenas k = 3 valores). Um Counting Sort estável faz isso e mantém a ordem alfabética dentro de cada conceito:
antes (ordem alfabética) |
→ |
depois (Counting Sort por conceito) |
Ordenar primeiro pela chave secundária (nome) e depois, de forma estável, pela chave principal (conceito) produz a ordenação por (conceito, nome). O Radix Sort repete esse truque dígito a dígito.
1.4 Código C
/* Counting sort para inteiros em [0, k]. a[] = entrada, b[] = saída, n = tamanho, k = valor máximo. */ void countingSort(int a[], int b[], int n, int k) { /* calloc (em vez de malloc) já zera todas as posições: os contadores precisam começar em 0. Com malloc, conteria lixo. */ int *count = calloc(k + 1, sizeof(int)); /* passo 1: contar ocorrências */ for (int i = 0; i < n; i++) count[a[i]]++; /* passo 2: prefixo acumulado */ for (int v = 1; v <= k; v++) count[v] += count[v-1]; /* passo 3: posicionar (direita para esquerda = estável) */ for (int i = n-1; i >= 0; i--) { b[count[a[i]] - 1] = a[i]; count[a[i]]--; } free(count); }
1.5 Complexidade e características
| Aspecto | Valor e explicação |
|---|---|
| Tempo no pior caso | O(n + k) — n para contar, k para acumular, n para posicionar |
| Tempo no caso médio | O(n + k) — o mesmo: o algoritmo faz sempre os mesmos passos, não importa a ordem da entrada |
| Espaço | O(n + k) — vetor de saída (tamanho n) + vetor de contagem (tamanho k+1) |
| Estável | Sim — o percurso da direita para a esquerda garante estabilidade |
| In-place | Não — requer vetor auxiliar de saída |
| Quando usar | k é pequeno, idealmente k = O(n) (k não muito maior que n); impraticável quando k ≫ n (k muito maior que n; ex.: inteiros de 64 bits) |
| Exemplos práticos | Ordenar notas de prova (0–100), conceitos (A–D), idades (0–130), caracteres ASCII (0–255) |
Limitação importante: se k = 109 e n = 100, o vetor count teria 109 entradas (cerca de 4 GB) — muito mais memória do que os dados em si. Para esses casos, a solução é o Radix Sort.
2. Radix Sort
2.1 Ideia
Em vez de contar todos os valores possíveis de uma vez, processamos a chave dígito a dígito, do menos significativo ao mais significativo (LSD — Least Significant Digit first), usando um algoritmo de ordenação estável em cada passo. Se cada chave tem d dígitos (d = número de dígitos da chave) e cada dígito pode assumir R valores diferentes (R = a base: 10 para dígitos decimais, 26 para letras minúsculas), são feitos d passes.
Insight central: se ordenamos pelo dígito d usando uma ordenação estável, e depois ordenamos pelo dígito d+1, elementos com o mesmo dígito na posição d+1 mantêm a ordem relativa correta estabelecida no passo anterior. Após processar todos os dígitos, o vetor está completamente ordenado.
| Analogia: para ordenar documentos por data (dd/mm/aaaa), ordene a pilha pelo dia; depois, de forma estável, pelo mês; por fim, de forma estável, pelo ano. O resultado está em ordem cronológica. |
2.2 Exemplo com dígitos decimais — 3 dígitos
Entrada: [329, 457, 657, 839, 436, 720, 355]
Em cada passo, os números são distribuídos em 10 “baldes” (0 a 9) conforme o dígito atual e recolhidos na ordem 0, 1, ..., 9, mantendo a ordem de chegada dentro de cada balde. Legenda: 7 = dígito sendo ordenado; 29 = parte já ordenada pelos passos anteriores.
Passo 1 — ordenar pelo dígito da unidade (estável):
| entrada | [329, 457, 657, 839, 436, 720, 355] | ||||||||||||||||||||
| baldes |
| ||||||||||||||||||||
| resultado | [720, 355, 436, 457, 657, 329, 839] |
Passo 2 — ordenar pelo dígito da dezena (estável):
| entrada | [720, 355, 436, 457, 657, 329, 839] | ||||||||||||||||||||
| baldes |
| ||||||||||||||||||||
| resultado | [720, 329, 436, 839, 355, 457, 657] |
Passo 3 — ordenar pelo dígito da centena (estável):
| entrada | [720, 329, 436, 839, 355, 457, 657] | ||||||||||||||||||||
| baldes |
| ||||||||||||||||||||
| resultado | [329, 355, 436, 457, 657, 720, 839] ← ordenado! |
Observe a parte verde crescendo da direita para a esquerda: após o passo p, os números estão ordenados considerando seus p últimos dígitos.
2.3 Exemplo de 2 dígitos — importando a estabilidade
Entrada: [36, 21, 97, 33, 84, 19, 45, 67]
Passo 1 — ordenar pelo dígito da unidade (estável):
| entrada | [36, 21, 97, 33, 84, 19, 45, 67] | ||||||||||||||||||||
| baldes |
| ||||||||||||||||||||
| resultado | [21, 33, 84, 45, 36, 97, 67, 19] |
Passo 2 — ordenar pelo dígito da dezena (estável):
| entrada | [21, 33, 84, 45, 36, 97, 67, 19] | ||||||||||||||||||||
| baldes |
| ||||||||||||||||||||
| resultado | [19, 21, 33, 36, 45, 67, 84, 97] ← ordenado! |
No passo 2, tanto 33 quanto 36 têm dezena = 3. A ordenação estável mantém a ordem do passo 1: 33 veio antes de 36 (unidade 3 < unidade 6), então 33 continua antes de 36. Compare:
| Passo 2 estável: [19, 21, 33, 36, 45, 67, 84, 97] Correto: 33 antes de 36. |
Passo 2 instável (hipotético): [19, 21, 36, 33, 45, 67, 84, 97] Errado: 36 antes de 33! |
Se o passo 2 fosse instável, o resultado sairia errado mesmo que cada passo individual parecesse “ordenar” por dezena.
2.4 Radix Sort para strings
Para strings de comprimento fixo w (número de caracteres de cada string) sobre um alfabeto Σ (o conjunto dos caracteres possíveis) de tamanho R (quantos caracteres diferentes existem, como R = 26 para letras minúsculas):
- Processar os caracteres do último para o primeiro (LSD).
- Usar Counting Sort nos caracteres de cada posição (tamanho do alfabeto = R).
- d = w passes (um por posição da string), cada um com custo O(n + R) (percorrer os n elementos e as R posições do vetor de contagem) → total O(w(n + R)); como R é fixo para um alfabeto dado, fica O(wn).
- Para strings de comprimento variável: completar com um caractere sentinela (valor 0, menor que todos os outros) até igualar o comprimento máximo.
Exemplo: ordenar as palavras [mar, sol, rua, mel, sal, lua, rio, ama] (w = 3).
Passo 1 — ordenar pela posição 2 (3ª letra) (estável):
| entrada | [mar, sol, rua, mel, sal, lua, rio, ama] | ||||||||
| baldes |
| ||||||||
| resultado | [rua, lua, ama, sol, mel, sal, rio, mar] |
Passo 2 — ordenar pela posição 1 (2ª letra) (estável):
| entrada | [rua, lua, ama, sol, mel, sal, rio, mar] | ||||||||||||
| baldes |
| ||||||||||||
| resultado | [sal, mar, mel, rio, ama, sol, rua, lua] |
Passo 3 — ordenar pela posição 0 (1ª letra) (estável):
| entrada | [sal, mar, mel, rio, ama, sol, rua, lua] | ||||||||||
| baldes |
| ||||||||||
| resultado | [ama, lua, mar, mel, rio, rua, sal, sol] ← ordenado! |
No passo 3, mar/mel, rio/rua e sal/sol começam com a mesma letra; quem os desempata é a ordem herdada do passo 2 (a < e, i < u, a < o) — de novo, graças à estabilidade.
Exemplo com comprimentos diferentes: ["ab", "b", "abc"]. Completamos com a sentinela ␣ (menor que qualquer letra): “ab␣”, “b␣␣”, “abc”.
Passo 1 — ordenar pela posição 2 (3ª letra) (estável):
| entrada | [ab␣, b␣␣, abc] | ||||
| baldes |
| ||||
| resultado | [ab␣, b␣␣, abc] |
Passo 2 — ordenar pela posição 1 (2ª letra) (estável):
| entrada | [ab␣, b␣␣, abc] | ||||
| baldes |
| ||||
| resultado | [b␣␣, ab␣, abc] |
Passo 3 — ordenar pela posição 0 (1ª letra) (estável):
| entrada | [b␣␣, ab␣, abc] | ||||
| baldes |
| ||||
| resultado | [ab␣, abc, b␣␣] ← ordenado! |
Removendo as sentinelas: ["ab", "abc", "b"] — a ordem do dicionário.
2.5 Código C
Para inteiros (base 10):
/* Radix Sort LSD para inteiros não-negativos. d = número de dígitos considerados (base 10). */ void radixSort(int a[], int n, int d) { int *b = malloc(n * sizeof(int)); int exp = 1; for (int pass = 0; pass < d; pass++) { int count[10] = {0}; /* contagem dos dígitos nesta posição */ for (int i = 0; i < n; i++) count[(a[i] / exp) % 10]++; /* prefixo acumulado */ for (int v = 1; v < 10; v++) count[v] += count[v-1]; /* posicionar de direita para esquerda (estável) */ for (int i = n-1; i >= 0; i--) { int dig = (a[i] / exp) % 10; b[count[dig] - 1] = a[i]; count[dig]--; } /* copiar de volta */ for (int i = 0; i < n; i++) a[i] = b[i]; exp *= 10; } free(b); }
Para strings de comprimento fixo w — o mesmo Counting Sort, aplicado ao caractere a[i][d]:
#define R 256 /* tamanho do alfabeto (ASCII) */ /* Radix Sort LSD para n strings de comprimento fixo w. Só os ponteiros são movidos; as strings não são copiadas. */ void radixSortStrings(char *a[], int n, int w) { char **b = malloc(n * sizeof(char *)); for (int d = w - 1; d >= 0; d--) { /* última -> primeira letra */ int count[R] = {0}; for (int i = 0; i < n; i++) count[(unsigned char) a[i][d]]++; for (int c = 1; c < R; c++) count[c] += count[c-1]; for (int i = n-1; i >= 0; i--) { unsigned char c = a[i][d]; b[count[c] - 1] = a[i]; count[c]--; } for (int i = 0; i < n; i++) a[i] = b[i]; } free(b); }
2.6 Complexidade e características do Radix Sort
| Aspecto | Valor e explicação |
|---|---|
| Tempo no pior caso | O(d × (n + R)) — d passes, cada um com Counting Sort em base R |
| Tempo no caso médio | O(d × (n + R)) — o mesmo: sempre faz os d passes completos |
| Caso prático | Inteiros de 32 bits com base 256: cada número tem 32 bits = 4 bytes, ou seja, d = 4 dígitos de base R = 256 → O(4(n+256)) = O(n) |
| Strings de comprimento w | O(w × (n + R)) |
| Estável | Sim — usa Counting Sort estável em cada passo |
| Espaço | O(n + R) — vetor temporário e vetor de contagem |
| Quando usar | Chaves com comprimento fixo ou limitado: inteiros, CEPs, CPFs, datas, sequências de DNA |
3. Comparação — Quando dá para ser mais rápido que O(n log n)
| Algoritmo | Pior caso | Caso médio | Espaço | Estável | Condição de uso |
|---|---|---|---|---|---|
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | Sim | k = O(n); inteiros em intervalo pequeno |
| Radix Sort | O(d(n + R)) | O(d(n + R)) | O(n + R) | Sim | Chaves de comprimento fixo ou limitado |
| Quick Sort | O(n2) | O(n log n) | O(log n) | Não | Caso geral; na prática muito rápido |
| Merge Sort | O(n log n) | O(n log n) | O(n) | Sim | Caso geral; garante O(n log n) mesmo no pior caso |
| Como Counting Sort e Radix Sort conseguem ser mais rápidos que O(n log n)? O fato de não ser possível ordenar mais rápido que O(n log n) no pior caso vale apenas para algoritmos baseados em comparações. Counting Sort e Radix Sort exploram a estrutura dos dados (valores discretos em intervalo conhecido) e não realizam comparações entre elementos. Em troca, exigem hipóteses extras sobre o domínio das chaves que o caso geral não satisfaz. |
Resumo
|
Exercícios
-
Aplique o Counting Sort ao vetor
[3, 6, 4, 1, 3, 4, 1, 4](k=6). Mostre o vetor de contagem após o passo 1, o vetor de prefixo acumulado após o passo 2, e o vetor de saída final. - Por que o Counting Sort percorre o vetor de entrada da direita para a esquerda no passo de posicionamento? O que aconteceria se percorresse da esquerda para a direita?
-
Aplique o Radix Sort LSD (base 10) ao vetor
[170, 45, 75, 90, 802, 24, 2, 66]. Mostre o vetor após cada passo. - Um programador usa Counting Sort para ordenar 1.000 números de CPF (até 11 dígitos, portanto k pode chegar a 99.999.999.999). Esse é um bom uso do algoritmo? Qual é o problema e que alternativa você sugeriria?
- Por que a sub-rotina usada no Radix Sort deve ser estável? Dê um exemplo concreto mostrando o que acontece de errado com uma ordenação instável.
- O Counting Sort é descrito como estável. O que significa "estável" em algoritmos de ordenação, e como o percurso da direita para a esquerda garante essa propriedade?
- Compare a complexidade de ordenar 1 milhão de inteiros de 8 dígitos usando: (a) Radix Sort base 10; (b) Merge Sort. Qual é mais rápido em teoria? O fator constante importa na prática?
- É possível aplicar o Radix Sort para ordenar números de ponto flutuante? Que desafios surgem?
Gabaritos
Sugestão de resposta — Exercício 1
Entrada: [3, 6, 4, 1, 3, 4, 1, 4] (n=8, k=6)
| a[] | 3a | 6 | 4a | 1a | 3b | 4b | 1b | 4c |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
Passo 1 — Contar:
| v | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| count[v] | 0 | 2 | 0 | 2 | 3 | 0 | 1 |
| contagem | – | ■■ | – | ■■ | ■■■ | – | ■ |
Passo 2 — Prefixo acumulado:
| v | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| conta | 0 | 0+2 | 2+0 | 2+2 | 4+3 | 7+0 | 7+1 |
| count[v] | 0 | 2 | 2 | 4 | 7 | 7 | 8 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| output[] | ||||||||
| faixa do 1 | faixa do 3 | faixa do 4 | faixa do 6 | |||||
Passo 3 — Posicionar (direita para esquerda):
| i | a[i] | posição | count após | saída após o passo | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 7 | 4c | output[7−1] = output[6] | count[4] = 6 |
| ||||||||
| 6 | 1b | output[2−1] = output[1] | count[1] = 1 |
| ||||||||
| 5 | 4b | output[6−1] = output[5] | count[4] = 5 |
| ||||||||
| 4 | 3b | output[4−1] = output[3] | count[3] = 3 |
| ||||||||
| 3 | 1a | output[1−1] = output[0] | count[1] = 0 |
| ||||||||
| 2 | 4a | output[5−1] = output[4] | count[4] = 4 |
| ||||||||
| 1 | 6 | output[8−1] = output[7] | count[6] = 7 |
| ||||||||
| 0 | 3a | output[3−1] = output[2] | count[3] = 2 |
|
Saída:
| output[] | 1a | 1b | 3a | 3b | 4a | 4b | 4c | 6 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
Sugestão de resposta — Exercício 2
Percorrer da direita para a esquerda garante estabilidade: entre elementos com a mesma chave, o que aparece mais à direita na entrada é posicionado primeiro, na última posição da faixa (pois count[v] aponta para o fim da faixa e é decrementado). Assim, o elemento que estava mais à esquerda na entrada termina mais à esquerda também na saída — preservando a ordem relativa original.
Se percorrêssemos da esquerda para a direita (sem mudar o resto), a ordem relativa seria invertida: no exemplo da aula, a saída teria 1d, 1c, 1b, 1a. O vetor ainda estaria ordenado por chave, mas não seria estável. Para uso isolado do Counting Sort isso pode ser indiferente; para uso como sub-rotina do Radix Sort, a instabilidade destruiria a correção dos passes anteriores.
Sugestão de resposta — Exercício 3
d=3 (maior número é 802, 3 dígitos). Números com menos dígitos são tratados com zeros à esquerda (em cinza).
Passo 1 — ordenar pelo dígito da unidade (estável):
| entrada | [170, 045, 075, 090, 802, 024, 002, 066] | ||||||||||||||||||||
| baldes |
| ||||||||||||||||||||
| resultado | [170, 090, 802, 002, 024, 045, 075, 066] |
Passo 2 — ordenar pelo dígito da dezena (estável):
| entrada | [170, 090, 802, 002, 024, 045, 075, 066] | ||||||||||||||||||||
| baldes |
| ||||||||||||||||||||
| resultado | [802, 002, 024, 045, 066, 170, 075, 090] |
Passo 3 — ordenar pelo dígito da centena (estável):
| entrada | [802, 002, 024, 045, 066, 170, 075, 090] | ||||||||||||||||||||
| baldes |
| ||||||||||||||||||||
| resultado | [002, 024, 045, 066, 075, 090, 170, 802] ← ordenado! |
Sugestão de resposta — Exercício 4
Não é uma boa ideia. O Counting Sort alocaria um vetor de contagem com aproximadamente 1011 entradas — se cada entrada ocupa 4 bytes, isso exigiria cerca de 400 GB de memória, completamente impraticável para 1.000 elementos.
O problema é que k ≫ n (k muito maior que n): o domínio das chaves (1011) é imensamente maior que o número de dados (103), tornando a memória O(n + k) = O(k) dominante e inviável.
A alternativa correta é o Radix Sort: tratar o CPF como uma string de 11 dígitos decimais e aplicar Counting Sort em cada posição com base 10 (R=10). Custo: 11 passes × O(n + 10) = O(11n) = O(n). Memória: O(n + 10) = O(n). Perfeitamente viável.
Sugestão de resposta — Exercício 5
Cada passo do Radix Sort ordena por um dígito e precisa preservar a ordem estabelecida pelos passes anteriores para os elementos que têm o mesmo dígito no passo atual. Se a sub-rotina for instável, essa informação anterior é perdida.
Exemplo com [36, 33]:
| Passo 1 (unidade) | Passo 2 estável (dezena) | Passo 2 instável (dezena) |
|---|---|---|
| [33, 36] 3 < 6, então 33 vem antes de 36 |
[33, 36] Correto: empate na dezena, mantém a ordem |
[36, 33] Errado: 36 > 33, mas aparece primeiro |
A estabilidade garante que "empates" no dígito atual sejam desfeitos pelo resultado de passes anteriores — que já ordenaram os dígitos menos significativos.
Sugestão de resposta — Exercício 6
Um algoritmo de ordenação é estável se, entre elementos com chaves iguais, a ordem relativa original é preservada na saída. Formalmente: se a[i] = a[j] e i < j na entrada, então a[i] aparece antes de a[j] na saída.
O percurso da direita para a esquerda garante isso da seguinte forma: suponha que dois elementos com chave v estão nas posições i e j, com i < j. O loop percorre j primeiro (à direita), coloca a[j] na posição count[v]-1 e decrementa count[v]. Depois percorre i, coloca a[i] na posição count[v]-1 (agora uma posição menor). Resultado: a[i] acaba em uma posição menor que a[j] na saída — exatamente a mesma ordem relativa que existia na entrada (veja 1a...1d no exemplo da seção 1.2).
Sugestão de resposta — Exercício 7
Dados: n = 106, inteiros de 8 dígitos decimais (d=8, R=10).
(a) Radix Sort base 10: d × (n + R) = 8 × (106 + 10) ≈ 8 × 106 = 8.000.000 operações.
(b) Merge Sort: n log2 n = 106 × 20 = 20.000.000 operações.
Radix (base 10) ######## 8 milhões Merge Sort #################### 20 milhões
Em teoria, o Radix Sort é mais rápido (8M vs. 20M operações básicas).
Na prática, o fator constante importa muito: o Radix Sort acessa memória de forma menos linear (os vetores de contagem e saída são acessados de forma potencialmente menos cache-friendly), enquanto o Merge Sort tem excelente localidade de memória. Para números de 32 bits com base 256 (d=4, R=256), o Radix Sort atinge 4 × (n + 256) ≈ 4n — nesse caso costuma superar o Merge Sort na prática também. A escolha depende do domínio, da cache e da arquitetura da máquina.
Sugestão de resposta — Exercício 8
Sim, mas com cuidados. Os desafios principais são:
- Representação binária não é order-preserving direta: números IEEE 754 não são ordenados simplesmente pelos bits se tratados como inteiros sem sinal, especialmente para números negativos (o bit de sinal é o mais significativo e fica invertido para negativos).
- Solução para positivos: floats positivos em IEEE 754 podem ser tratados como inteiros de 32 bits e ordenados diretamente pelo Radix Sort — a ordem binária coincide com a ordem numérica para valores positivos.
- Solução geral: XOR com uma máscara específica antes de ordenar e desfazer após: se o bit de sinal é 1 (negativo), inverter todos os bits; se é 0 (positivo), inverter só o bit de sinal. Isso mapeia floats em inteiros com ordem preservada.
- NaN e infinito: esses valores especiais do IEEE 754 precisam de tratamento separado, pois sua posição na ordem não é bem definida (NaN não é comparável).
Na prática, a técnica existe e é usada em códigos de alto desempenho (ex.: engines de renderização para ordenar primitivas gráficas por profundidade), mas requer cuidado na implementação para lidar corretamente com negativos e valores especiais.