Algoritmo de ordenação não comparativo que conta a frequência de cada elemento para determinar suas posições no array ordenado.
O Counting Sort não compara elementos entre si. Em vez disso, conta quantas vezes cada valor aparece e usa essa informação para posicionar os elementos diretamente. Funciona em três fases: contagem (conta ocorrências), acumulação (calcula posições finais) e posicionamento (coloca cada elemento na posição correta). É extremamente eficiente quando o intervalo de valores (k) é pequeno em relação ao tamanho do array (n). Porém, não funciona bem com valores muito grandes ou números negativos sem adaptação.
“O Counting Sort é O(n + k) porque não compara elementos. Quando k = O(n), é linear. É a base para o Radix Sort.”
n é o tamanho do array, k é o valor máximo. Percorre o array duas vezes e o array de contagem uma vez.
Precisa do array de contagem de tamanho k+1 e do array de saída de tamanho n.
Sempre o mesmo, independente da entrada.
Quando k é muito grande comparado a n, o espaço e tempo são dominados por k.
| Algoritmo | Tempo | Espaco | Estavel | Melhor Para |
|---|---|---|---|---|
| Counting Sort(atual) | O(n + k) | O(n + k) | Sim | Inteiros com intervalo pequeno |
| Bubble Sort | O(n²) | O(1) | Sim | Fins didáticos |
| Quick Sort | O(n log n) | O(log n) | Nao | Uso geral |
| Merge Sort | O(n log n) | O(n) | Sim | Grandes datasets |
Pratique respondendo a perguntas comuns de entrevistas tecnicas. Clique em uma pergunta para iniciar uma sessao de pratica com IA.
1def counting_sort(array):Definição2 if not array:3 return array4 5 max_val = max(array)Encontrar Máximo6 7 count = [0] * (max_val + 1)Array de Contagem8 9 for num in array:Contagem10 count[num] += 111 12 for i in range(1, len(count)):Soma Acumulada13 count[i] += count[i - 1]14 15 output = [0] * len(array)Array de Saída16 17 for i in range(len(array) - 1, -1, -1):Posicionamento18 output[count[array[i]] - 1] = array[i]19 count[array[i]] -= 120 21 return output22