Implemente o algoritmo de classificação por contagem em Java

Publicados: 2023-01-30
Implemente o algoritmo de classificação por contagem em Java

O que é algoritmo de classificação por contagem?

Counting sort, um algoritmo de classificação que é eficiente para small ranges of integers . Ele funciona contando o número de ocorrências de cada valor na matriz de entrada e, em seguida, usando essas informações para colocar cada valor em sua posição correta na matriz de saída.

A complexidade de tempo desse algoritmo é O(n+k) , onde n é o tamanho da matriz de entrada e k é o intervalo dos inteiros.

CrunchifyCountingSortAlgo.java

Aqui está uma implementação completa do Counting Sort em Java. Basta copiá-lo para o IDEA de sua preferência e executá-lo.

 pacote crunchify.com.java.tutorials;

importar java.util.Arrays;

/**
 * @autor Crunchify.com
 * Programa: Como implementar o algoritmo Counting sort em java?
 * Counting sort é um algoritmo de ordenação que ordena os elementos de um array 
 * contando o número de ocorrências de cada elemento único na matriz.
 */

public class CrunchifyCountingSortAlgo {

    public static void main(String[] args) {

        // Array inteiro de 10 elementos
        int[] crunchifyArray = {9, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3};

        crunchifyPrint("Array Original: " + Arrays.toString(crunchifyArray));
        crunchifyPrint ("\n");

        CrunchifyCountingSortAlgo crunchify = new CrunchifyCountingSortAlgo();
        crunchify.crunchifyCountingSortAlgorithm(crunchifyArray);

        crunchifyPrint ("\n");
        crunchifyPrint("Resultado do Algoritmo de Ordenação por Contagem Crunchify: " + Arrays.toString(crunchifyArray));
    }

    private static void crunchifyPrint(String s) {

        System.out.println(s);
    }


    /**
     * Autor: App Shah (Crunchify.com)
     *
     * Lógica de classificação de contagem:
     * Esta é uma implementação de classificação por contagem, um algoritmo de classificação eficiente para pequenos intervalos de inteiros.
     * Funciona contando o número de ocorrências de cada valor no array de entrada,
     * e, em seguida, usando essas informações para colocar cada valor em sua posição correta na matriz de saída.
     * A complexidade de tempo deste algoritmo é O(n+k),
     * onde n é o tamanho da matriz de entrada e k é o intervalo dos inteiros.
     */


    public static int[] crunchifyCountingSortAlgorithm(int[] crunchifyArray) {

        // getAsInt(): Se um valor estiver presente, retorna o valor, caso contrário, lança NoSuchElementException.
        int crunchifyMax = Arrays.stream(crunchifyArray).max().getAsInt();
        int[] crunchifyCount = new int[crunchifyMax + 1];

        // crunchifyConta as ocorrências de cada valor no array de entrada
        for (int i = 0; i < crunchifyArray.length; i++) {
            crunchifyCount[crunchifyArray[i]]++;
            crunchifyPrint("Adicionando 1 para crunchifyCount[" + crunchifyArray[i] 
                    + "], o array crunchifyCount agora é: " + Arrays.toString(crunchifyCount));
        }

        crunchifyPrint ("\n");

        int k = 0;
        for (int i = 0; i <= crunchifyMax; i++) {
            for (int j = 0; j < crunchifyCount[i]; j++) {
                crunchifyArray[k++] = i;
                crunchifyPrint("Adicionando " + i + " à posição " + (k - 1) 
                        + " no array de saída, o array de saída agora é: " + Arrays.toString(crunchifyArray));
            }
        }

        return crunchifyArray;
    }

}

Basta executar o programa acima como um aplicativo Java no IntelliJ IDEA ou Eclipse IDE e você terá o resultado abaixo.

Resultado do console IntelliJ IDEA

 Matriz original: [9, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3]


Adicionando 1 a crunchifyCount[9], o array crunchifyCount agora é: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Adicionando 1 a crunchifyCount[3], o array crunchifyCount agora é: [0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Adicionando 1 a crunchifyCount[6], o array crunchifyCount agora é: [0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Adicionando 1 a crunchifyCount[6], o array crunchifyCount agora é: [0, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Adicionando 1 a crunchifyCount[1], o array crunchifyCount agora é: [0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Adicionando 1 a crunchifyCount[12], o array crunchifyCount agora é: [0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Adicionando 1 a crunchifyCount[32], o array crunchifyCount agora é: [0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
Adicionando 1 a crunchifyCount[29], o array crunchifyCount agora é: [0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]
Adicionando 1 a crunchifyCount[2], o array crunchifyCount agora é: [0, 1, 1, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]
Adicionando 1 a crunchifyCount[9], o array crunchifyCount agora é: [0, 1, 1, 1, 0, 0, 2, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]
Adicionando 1 a crunchifyCount[3], o array crunchifyCount agora é: [0, 1, 1, 2, 0, 0, 2, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]


Adicionando 1 à posição 0 na matriz de saída, a matriz de saída é agora: [1, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3]
Adicionando 2 à posição 1 na matriz de saída, a matriz de saída é agora: [1, 2, 6, 6, 1, 12, 32, 29, 2, 9, 3]
Adicionando 3 à posição 2 na matriz de saída, a matriz de saída é agora: [1, 2, 3, 6, 1, 12, 32, 29, 2, 9, 3]
Adicionando 3 à posição 3 na matriz de saída, a matriz de saída é agora: [1, 2, 3, 3, 1, 12, 32, 29, 2, 9, 3]
Adicionando 6 à posição 4 na matriz de saída, a matriz de saída é agora: [1, 2, 3, 3, 6, 12, 32, 29, 2, 9, 3]
Adicionando 6 à posição 5 na matriz de saída, a matriz de saída é agora: [1, 2, 3, 3, 6, 6, 32, 29, 2, 9, 3]
Adicionando 9 à posição 6 na matriz de saída, a matriz de saída é agora: [1, 2, 3, 3, 6, 6, 9, 29, 2, 9, 3]
Adicionando 9 à posição 7 na matriz de saída, a matriz de saída é agora: [1, 2, 3, 3, 6, 6, 9, 9, 2, 9, 3]
Adicionando 12 à posição 8 na matriz de saída, a matriz de saída é agora: [1, 2, 3, 3, 6, 6, 9, 9, 12, 9, 3]
Adicionando 29 à posição 9 na matriz de saída, a matriz de saída é agora: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 3]
Adicionando 32 à posição 10 na matriz de saída, a matriz de saída é agora: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 32]


Resultado do algoritmo de classificação por contagem do Crunchify: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 32]

Processo finalizado com código de saída 0
Implementar o algoritmo de classificação por contagem em Java - resultado do IntelliJ IDEA

Deixe-me saber se você enfrentar qualquer problema executando acima do programa Counting Sort Algorithm Java.