Counting Sort

Introduzione

Counting sort è un algoritmo che ordina gli elementi in un array in tempo lineare. Tuttavia necessita di uno spazio in più in memoria per un altro array di appoggio che può essere anche particolarmente grande.

Idea

Il nome di questo algoritmo deriva dal fatto che conta il numero delle occorrenza dei valori distinti in un array.
Il counting sort crea un relazione tra valori nell’array da ordinare e valori degli indici dell’array di appoggio.
Se ad esempio l’array da ordinare (A) è composto dai valori [1, 53, 23, 49, 49, 100], nell’array di appoggio (C) andremo a scrivere le occorrenze dei valori distinti in A nelle corrispondenti celle. Esempio se A[j] = 49, in C[A[j]] metteremo 2 perché il valore 49 compare due volte in A.
Avremo allora bisogno che C abbia una dimensione di 100 celle, quindi in termini di spazio è abbastanza dispendioso per il nostro scopo.
Passiamo a descrivere il codice in dettaglio e fare un esempio per avere le idee subito più chiare.

Pseudocodice

Lo pseudocodice è ispirato dal libro Introduzione agli Algoritmi.

Counting-Sort(A, B, k)

        let C[0..k] be a new array
        for (i = 0 to k)
            C[i] = 0
        for (j = 1 to A.length)
            C[A[j]] = C[A[j]] + 1
        // C[i] now contains the number of elements equal to i.
        for (i = 1 to k)
            C[i] = C[i] + C[i-1]
        // C[i] now contains the number of elements less than or equal to i.
        for (j = A.length downto 1)
            B[C[A[j]]] = A[j]
            c[A[j]] = C[A[j]] - 1

La funzione prende in input l’array A, un array di output B e il numero di elementi distinti k.
Nelle prime righe viene dichiarato un array C di appoggio di dimensione k, ovvero di dimensione uguale al numero di valori distinti in A, successivamente tutte le celle vengono inizializzate a zero con un ciclo.
Il secondo ciclo esegue l’operazione di conteggio delle occorrenze degli elementi in A tali che A[j] = i, e li salva in C[i].
Il terzo ciclo incrementa il valore delle celle dell’array C tale che C[i] = C[i] + C[i-1], cioè sostanzialmente la cella corrente viene incrementata sommando il contenuto della cella stessa con quello della cella precedente.
L’ultimo ciclo inserisce nell’array B la sequenza ordinata. Per capire la logica del ciclo, è utile seguire la seguente sequenza: il ciclo parte dalla fine dell’array A, guarda il valore della cella corrente, si reca sulla cella dell’array C di indice i = A[j], il contenuto in tale cella indica che nella cella B[i] dove i = C[A[j]], deve essere quello di A[j]. Poi il counting delle occorrenze in C[A[j]] viene decrementata. Questione di pratica 🙂

Esempio

Portiamo un esempio di countig sort su un array A = [3, 6, 4, 1, 3, 4, 1, 4]

La convenienza di usare questo algoritmo arriva quando si devono ordinare numeri interi dove il range di appartenenza dei valori distinti è abbastanza basso e abbiamo da ordinare un array costituito da un numero di elementi >= k, dove k è il range.
La complessità dipende se è più grande il range dei valori distinti (k) oppure il numero di elementi (n) nell’array da ordinare.
In conclusione il countig sort conviene se k = O(n) e in generale la sua complessità vale Θ(k + n).