Counting Sort
Conta quantas vezes cada valor aparece e usa essas contagens para posicionar cada elemento diretamente — sem comparações.
O(n)O(n)Como Funciona
Passo a passo do algoritmo
Crie o array de contagem
Crie um array auxiliar de tamanho k (onde k é o valor máximo) inicializado com zeros. Este array registrará quantas vezes cada valor aparece no input.
contagem = array de tamanho (max+1) com zerosConte cada elemento
Percorra o array de entrada e, para cada elemento, incremente a posição correspondente no array de contagem.
para cada elemento em array: contagem[elemento]++Calcule posições cumulativas
Transforme o array de contagem em posições cumulativas. Cada posição indica o índice final do último elemento com aquele valor no output.
para i de 1 até k: contagem[i] += contagem[i-1]Construa o array de saída
Percorra o array de entrada de trás para frente. Para cada elemento, use o array de contagem para encontrar sua posição no output e decremente o contador.
para i de n-1 até 0:
saida[contagem[array[i]]-1] = array[i]
contagem[array[i]]--Copie para o array original
Copie o array de saída de volta para o array original. O resultado é um array completamente ordenado em tempo linear.
array = saidaImplementação
Código comentado em JavaScript e Python
function countingSort(array) {
if (array.length === 0) return array;
const max = Math.max(...array);
const min = Math.min(...array);
const range = max - min + 1;
// Cria e preenche o array de contagem
const contagem = new Array(range).fill(0);
for (const elemento of array) {
contagem[elemento - min]++;
}
// Calcula posições cumulativas
for (let i = 1; i < range; i++) {
contagem[i] += contagem[i - 1];
}
// Constrói o array de saída (de trás para frente para estabilidade)
const saida = new Array(array.length);
for (let i = array.length - 1; i >= 0; i--) {
const pos = contagem[array[i] - min] - 1;
saida[pos] = array[i];
contagem[array[i] - min]--;
}
// Copia de volta para o array original
for (let i = 0; i < array.length; i++) {
array[i] = saida[i];
}
return array;
}
// Exemplo de uso
const arr = [4, 2, 2, 8, 3, 3, 1];
console.log(countingSort(arr)); // [1, 2, 2, 3, 3, 4, 8]Playground
Veja a contagem e posicionamento do Counting Sort em tempo real
Quando Usar
Cenários ideais para este algoritmo
Intervalo de valores pequeno
Perfeito quando os valores estão em um intervalo limitado (e.g., notas de 0-100, idades, meses do ano).
Muitas duplicatas
Extremamente eficiente quando há muitos valores repetidos — conta cada valor apenas uma vez.
Pré-processamento para Radix Sort
O Radix Sort usa o Counting Sort internamente para cada posição de dígito, combinando eficiência linear em ambos.
Ordenação estável
A implementação clássica (de trás para frente) garante estabilidade — elementos iguais mantêm sua ordem relativa original.
Complexidade
Análise de desempenho por cenário
| Cenário | Tempo |
|---|---|
| Melhor caso | O(n) |
| Caso médio | O(n) |
| Pior caso | O(n) |