INF01203 - Estruturas de Dados - Instituto de Informática (UFRGS) - Prof. Dennis Giovani Balreira



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[]4a1a3a1b2a4b1c3b2b4c1d
012345678910

Passo 1 — Contar: count[v] = número de vezes que v aparece na entrada.

v01234
count[v]04223
contagem–■■■■■■■■■■■

Passo 2 — Prefixo acumulado: count[v] passa a ser o número de elementos ≤ v (soma cumulativa).

v01234
conta00+44+26+28+3
count[v]046811

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:

012345678910
output[]           
faixa do 1faixa do 2faixa do 3faixa 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):

ia[i]posiçãocount apóssaída após o passo
101doutput[4−1] = output[3]count[1] = 3
   1d       
94coutput[11−1] = output[10]count[4] = 10
   1d      4c
82boutput[6−1] = output[5]count[2] = 5
   1d 2b    4c
73boutput[8−1] = output[7]count[3] = 7
   1d 2b 3b  4c
61coutput[3−1] = output[2]count[1] = 2
  1c1d 2b 3b  4c
54boutput[10−1] = output[9]count[4] = 9
  1c1d 2b 3b 4b4c
42aoutput[5−1] = output[4]count[2] = 4
  1c1d2a2b 3b 4b4c
31boutput[2−1] = output[1]count[1] = 1
 1b1c1d2a2b 3b 4b4c
23aoutput[7−1] = output[6]count[3] = 6
 1b1c1d2a2b3a3b 4b4c
11aoutput[1−1] = output[0]count[1] = 0
1a1b1c1d2a2b3a3b 4b4c
04aoutput[9−1] = output[8]count[4] = 8
1a1b1c1d2a2b3a3b4a4b4c

Saída:

output[]1a1b1c1d2a2b3a3b4a4b4c
012345678910

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:

NomeConceito
AnaB
BrunoA
CarlaC
DaviB
EvaA
FelipeC
antes (ordem alfabética)
→
NomeConceito
BrunoA
EvaA
AnaB
DaviB
CarlaC
FelipeC
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 casoO(n + k) — n para contar, k para acumular, n para posicionar
Tempo no caso médioO(n + k) — o mesmo: o algoritmo faz sempre os mesmos passos, não importa a ordem da entrada
EspaçoO(n + k) — vetor de saída (tamanho n) + vetor de contagem (tamanho k+1)
EstávelSim — o percurso da direita para a esquerda garante estabilidade
In-placeNão — requer vetor auxiliar de saída
Quando usark é 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áticosOrdenar 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
0123456789
720    355436457
657
 329
839
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
0123456789
  720
329
436
839
 355
457
657
    
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
0123456789
   329
355
436
457
 657720839 
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
0123456789
 21 3384453697
67
 19
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
0123456789
 192133
36
45 67 8497
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
alor
rua
lua
ama
sol
mel
sal
riomar
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
aeimou
sal
mar
melrioamasolrua
lua
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
almrs
amaluamar
mel
rio
rua
sal
sol
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
␣c
ab␣
b␣␣
abc
resultado[ab␣, b␣␣, abc]

Passo 2 — ordenar pela posição 1 (2ª letra) (estável):

entrada[ab␣, b␣␣, abc]
baldes
␣b
b␣␣ab␣
abc
resultado[b␣␣, ab␣, abc]

Passo 3 — ordenar pela posição 0 (1ª letra) (estável):

entrada[b␣␣, ab␣, abc]
baldes
ab
ab␣
abc
b␣␣
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 casoO(d × (n + R)) — d passes, cada um com Counting Sort em base R
Tempo no caso médioO(d × (n + R)) — o mesmo: sempre faz os d passes completos
Caso práticoInteiros 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 wO(w × (n + R))
EstávelSim — usa Counting Sort estável em cada passo
EspaçoO(n + R) — vetor temporário e vetor de contagem
Quando usarChaves 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 SortO(n + k)O(n + k)O(n + k)Simk = O(n); inteiros em intervalo pequeno
Radix SortO(d(n + R))O(d(n + R))O(n + R)SimChaves de comprimento fixo ou limitado
Quick SortO(n2)O(n log n)O(log n)NãoCaso geral; na prática muito rápido
Merge SortO(n log n)O(n log n)O(n)SimCaso 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

  • Counting Sort: conta ocorrências de cada valor (passo 1), calcula prefixo acumulado (passo 2) e posiciona elementos da direita para a esquerda para garantir estabilidade (passo 3). Complexidade O(n+k) (n = elementos, k = maior valor da chave) em tempo e espaço. Útil quando k = O(n).
  • Radix Sort: aplica Counting Sort estável em cada posição dos dígitos, do menos ao mais significativo (LSD). Complexidade O(d(n+R)) (d = número de dígitos, R = base). Para inteiros de 32 bits com base 256, torna-se O(n). Para strings de comprimento w, torna-se O(w(n+R)).
  • Estabilidade é essencial no Radix Sort: sem ela, os passes anteriores seriam desfeitos e a ordenação final seria incorreta.
  • Mais rápido que O(n log n): algoritmos baseados em comparações não conseguem ser mais rápidos que O(n log n) no pior caso. Counting Sort e Radix Sort conseguem porque não comparam elementos: exploram a estrutura das chaves.
  • Quando escolher: k pequeno → Counting Sort; chaves de comprimento fixo → Radix Sort; caso geral sem restrições → Quick Sort ou Merge Sort.

Exercícios

  1. 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.

  2. 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?

  3. Aplique o Radix Sort LSD (base 10) ao vetor [170, 45, 75, 90, 802, 24, 2, 66]. Mostre o vetor após cada passo.

  4. 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?

  5. 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.

  6. 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?

  7. 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?

  8. É 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[]3a64a1a3b4b1b4c
01234567

Passo 1 — Contar:

v0123456
count[v]0202301
contagem–■■–■■■■■–■

Passo 2 — Prefixo acumulado:

v0123456
conta00+22+02+24+37+07+1
count[v]0224778
01234567
output[]        
faixa do 1faixa do 3faixa do 4faixa do 6

Passo 3 — Posicionar (direita para esquerda):

ia[i]posiçãocount apóssaída após o passo
74coutput[7−1] = output[6]count[4] = 6
      4c 
61boutput[2−1] = output[1]count[1] = 1
 1b    4c 
54boutput[6−1] = output[5]count[4] = 5
 1b   4b4c 
43boutput[4−1] = output[3]count[3] = 3
 1b 3b 4b4c 
31aoutput[1−1] = output[0]count[1] = 0
1a1b 3b 4b4c 
24aoutput[5−1] = output[4]count[4] = 4
1a1b 3b4a4b4c 
16output[8−1] = output[7]count[6] = 7
1a1b 3b4a4b4c6
03aoutput[3−1] = output[2]count[3] = 2
1a1b3a3b4a4b4c6

Saída:

output[]1a1b3a3b4a4b4c6
01234567

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
0123456789
170
090
 802
002
 024045
075
066   
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
0123456789
802
002
 024 045 066170
075
 090
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
0123456789
002
024
045
066
075
090
170      802 
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.