Implementa l'algoritmo di ordinamento del conteggio in Java

Che cos'è l'algoritmo di ordinamento del conteggio?

Counting sort, un algoritmo di ordinamento efficiente per small ranges of integers . Funziona contando il numero di occorrenze di ciascun valore nell'array di input e quindi utilizzando tali informazioni per posizionare ciascun valore nella posizione corretta nell'array di output.

La complessità temporale di questo algoritmo è O(n+k) , dove n è la dimensione dell'array di input e k è l'intervallo degli interi.

CrunchifyCountingSortAlgo.java

Ecco un'implementazione completa di Counting Sort in Java. Basta copiarlo nella tua IDEA preferita ed eseguirlo.

 pacchetto crunchify.com.java.tutorials;

import java.util.Arrays;

/**
 * @autore Crunchify.com
 * Programma: come implementare l'algoritmo di ordinamento del conteggio in Java?
 * Counting sort è un algoritmo di ordinamento che ordina gli elementi di un array 
 * contando il numero di occorrenze di ciascun elemento univoco nell'array.
 */

classe pubblica CrunchifyCountingSortAlgo {

    public static void main(String[] args) {

        // Integer Array di 10 elementi
        int[] crunchifyArray = {9, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3};

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

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

        crunchifyPrint ("\n");
        crunchifyPrint("Risultato dell'algoritmo di ordinamento del conteggio Crunchify: " + Arrays.toString(crunchifyArray));
    }

    private static void crunchifyPrint(String s) {

        System.out.println(s);
    }


    /**
     * Autore: App Shah (Crunchify.com)
     *
     * Logica di ordinamento del conteggio:
     * Si tratta di un'implementazione di counting sort, un algoritmo di ordinamento efficiente per piccoli intervalli di numeri interi.
     * Funziona contando il numero di occorrenze di ciascun valore nell'array di input,
     * e quindi utilizzando tali informazioni per posizionare ciascun valore nella posizione corretta nell'array di output.
     * La complessità temporale di questo algoritmo è O(n+k),
     * dove n è la dimensione dell'array di input e k è l'intervallo degli interi.
     */


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

        // getAsInt(): se è presente un valore, restituisce il valore, altrimenti genera NoSuchElementException.
        int crunchifyMax = Arrays.stream(crunchifyArray).max().getAsInt();
        int[] crunchifyCount = new int[crunchifyMax + 1];

        // crunchifyConta le occorrenze di ciascun valore nell'array di input
        for (int i = 0; i < crunchifyArray.length; i++) {
            crunchifyCount[crunchifyArray[i]]++;
            crunchifyPrint("Aggiungo 1 a crunchifyCount[" + crunchifyArray[i] 
                    + "], l'array crunchifyCount ora è: " + Arrays.toString(crunchifyCount));
        }

        crunchifyPrint ("\n");

        intero k = 0;
        for (int i = 0; i <= crunchifyMax; i++) {
            for (int j = 0; j < crunchifyCount[i]; j++) {
                crunchifyArray[k++] = i;
                crunchifyPrint("Aggiungo " + i + " alla posizione " + (k - 1) 
                        + " nell'array di output, l'array di output è ora: " + Arrays.toString(crunchifyArray));
            }
        }

        return crunchifyArray;
    }

}

Basta eseguire il programma sopra come applicazione Java in IntelliJ IDEA o Eclipse IDE e otterrai come di seguito.

Risultato console IntelliJ IDEA

 Array originale: [9, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3]


Aggiungendo 1 a crunchifyCount[9], l'array crunchifyCount è ora: [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]
Aggiungendo 1 a crunchifyCount[3], l'array crunchifyCount è ora: [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]
Aggiungendo 1 a crunchifyCount[6], l'array crunchifyCount è ora: [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]
Aggiungendo 1 a crunchifyCount[6], l'array crunchifyCount è ora: [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]
Aggiungendo 1 a crunchifyCount[1], l'array crunchifyCount è ora: [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]
Aggiungendo 1 a crunchifyCount[12], l'array crunchifyCount è ora: [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]
Aggiungendo 1 a crunchifyCount[32], l'array crunchifyCount è ora: [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]
Aggiungendo 1 a crunchifyCount[29], l'array crunchifyCount è ora: [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]
Aggiungendo 1 a crunchifyCount[2], l'array crunchifyCount è ora: [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]
Aggiungendo 1 a crunchifyCount[9], l'array crunchifyCount è ora: [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]
Aggiungendo 1 a crunchifyCount[3], l'array crunchifyCount è ora: [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]


Aggiungendo 1 alla posizione 0 nell'array di output, l'array di output è ora: [1, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3]
Aggiungendo 2 alla posizione 1 nell'array di output, l'array di output è ora: [1, 2, 6, 6, 1, 12, 32, 29, 2, 9, 3]
Aggiungendo 3 alla posizione 2 nell'array di output, l'array di output è ora: [1, 2, 3, 6, 1, 12, 32, 29, 2, 9, 3]
Aggiungendo 3 alla posizione 3 nell'array di output, l'array di output è ora: [1, 2, 3, 3, 1, 12, 32, 29, 2, 9, 3]
Aggiungendo 6 alla posizione 4 nell'array di output, l'array di output è ora: [1, 2, 3, 3, 6, 12, 32, 29, 2, 9, 3]
Aggiungendo 6 alla posizione 5 nell'array di output, l'array di output è ora: [1, 2, 3, 3, 6, 6, 32, 29, 2, 9, 3]
Aggiungendo 9 alla posizione 6 nell'array di output, l'array di output è ora: [1, 2, 3, 3, 6, 6, 9, 29, 2, 9, 3]
Aggiungendo 9 alla posizione 7 nell'array di output, l'array di output è ora: [1, 2, 3, 3, 6, 6, 9, 9, 2, 9, 3]
Aggiungendo 12 alla posizione 8 nell'array di output, l'array di output è ora: [1, 2, 3, 3, 6, 6, 9, 9, 12, 9, 3]
Aggiungendo 29 alla posizione 9 nell'array di output, l'array di output è ora: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 3]
Aggiungendo 32 alla posizione 10 nell'array di output, l'array di output è ora: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 32]


Risultato dell'algoritmo di ordinamento del conteggio di Crunchify: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 32]

Processo terminato con codice di uscita 0 

Fammi sapere se riscontri problemi con l'esecuzione del programma Java Counting Sort Algorithm.