TOP 25 ALGORITMOS | Counting Sort

É um algoritmo de classificação não baseado em comparação. Ele é particularmente eficiente quando o intervalo de valores de entrada é pequeno comparado ao número de elementos a serem classificados. A ideia básica é contar a frequência de cada elemento distinto no array de entrada e usar essa informação para colocar os elementos em suas posições corretas classificadas.

📁 | Resumo

🤖 | Código

.
function countSort(inputArray) {
  const N = inputArray.length;

  // Encontrando o elemento máximo de inputArray
  let M = 0;
  for (let i = 0; i < N; i++) {
      M = Math.max(M, inputArray[i]);
  }

  // Inicializando countArray com 0
  const countArray = new Array(M + 1).fill(0);

  // Mapeando cada elemento de inputArray como um índice de countArray
  for (let i = 0; i < N; i++) {
      countArray[inputArray[i]]++;
  }

  // Calculando a soma do prefixo em cada índice de countArray
  for (let i = 1; i <= M; i++) {
      countArray[i] += countArray[i - 1];
  }

  // Criando outputArray a partir de countArray
  const outputArray = new Array(N);
  for (let i = N - 1; i >= 0; i--) {
      outputArray[countArray[inputArray[i]] - 1] = inputArray[i];
      countArray[inputArray[i]]--;
  }

  return outputArray;
}
.

🕰️ | Complexidade de Tempo

Requer DOIS ESPAÇOS de memória extra temporária. Logo, sua complexidade de espaço será descrita por O(P + M), sendo P o inputArray[ ] e M o countArray[ ].

📦 | Complexidade de Espaço

Requer DOIS ESPAÇOS de memória extra temporária. Logo, sua complexidade de espaço será descrita por O(N + M), sendo N o correspArray[ ] e M o countArray[ ].

✔️ | Vantagens

✦ Fácil de implementar, estável e rápido;

❌ | Desvantagens

✦ Precisa de espaço auxiliar;

✦ Não funciona em valores decimais;

✦ Ineficiente se o intervalo de valores a serem ordenados for muito grande;