Article image
Isadora Ariane
Isadora Ariane21/11/2024 13:41
Compartilhe

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

    image

    image

    🤖 | 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;

    Compartilhe
    Comentários (0)