1. Conta le occorrenze
Si crea C[0…30], inizialmente tutto a zero. Dopo aver letto gli studenti, le sole celle non nulle sono C[18]=2, C[24]=2, C[27]=1 e C[30]=1.
Algoritmi di ordinamento · 5/7
Counting sort
Sostituisce i confronti con il conteggio di chiavi intere.
Tempo medioΘ(n + k)
MemoriaΘ(n + k)
StabileSì
In placeNo
Come funziona
Conta quante volte compare ogni valore. Dopo le somme cumulative, C[v] dice quanti elementi sono ≤ v: la posizione in cui inserire la prossima occorrenza di v è quindi C[v]−1. Attraversando l’input da destra e decrementando il contatore si costruisce un output stabile.
Invariante: Dopo le somme cumulative, C[v] è il numero di elementi ≤ v. Durante la costruzione, C[v]−1 indica la posizione libera più a destra riservata a v.
Esempio: studenti ordinati per voto
Supponiamo di voler ordinare gli studenti di un corso usando come chiave il voto, che può essere soltanto un intero tra 0 e 30. L’intervallo contiene appena 31 valori possibili: invece di confrontare gli studenti a coppie, Counting sort può riservare un contatore a ogni voto.
Elenco iniziale: Anna 24, Luca 18, Sara 27, Paolo 24, Giulia 30, Marco 18.
2. Calcola le somme cumulative
Ogni cella viene sommata alla precedente. Così C[18]=2, C[24]=4, C[27]=5 e C[30]=6: per esempio, ci sono quattro studenti con voto ≤24 e l’ultima posizione riservata a un 24 è C[24]−1=3.
3. Costruisci l’output
Si visita l’elenco da destra a sinistra. Ogni studente con voto v va in B[C[v]−1], poi C[v] diminuisce. Il risultato è: Luca 18, Marco 18, Anna 24, Paolo 24, Sara 27, Giulia 30.
Perché si procede da destra? In questo modo gli studenti con lo stesso voto conservano l’ordine iniziale: Luca resta prima di Marco e Anna prima di Paolo. È proprio questa la stabilità di Counting sort. Con soli 31 contatori il costo è Θ(n+31), quindi sostanzialmente lineare nel numero di studenti.
Simulazione passo passo
Ogni barra rappresenta un elemento. I colori distinguono gli elementi confrontati, il pivot o la chiave, la parte già definitiva e l’area attiva.
Da 2 a 16 valori tra 0 e 999, in un intervallo ampio al massimo 80.
- Confronti
- 0
- Scritture
- 0
- Scambi
- 0
- Passaggio / livello
- 0
attivo
confronto
pivot / chiave
definitivo
Pseudocodice collegato alla simulazione
C[0 … k] ← 0for value in A: C[value]++for i ← 1 to k: C[i] ← C[i] + C[i − 1]for i ← n − 1 downto 0B[C[A[i]] − 1] ← A[i]C[A[i]]--copy B into A
La riga evidenziata corrisponde all’operazione descritta nel simulatore. I dettagli di gestione degli indici sono intenzionalmente semplificati.
Studio della complessità
Occorre comunque leggere n elementi e inizializzare k contatori: Θ(n+k).
Il numero di passaggi non dipende dall’ordine dell’input: Θ(n+k).
Anche il caso peggiore compie gli stessi passaggi lineari in n e k.
Servono Θ(k) contatori e, nella versione stabile, Θ(n) per l’output: Θ(n+k). Non è in place.
Proprietà in breve
La stabilità riguarda l’ordine relativo degli elementi con chiave uguale.
La classificazione considera la versione dell’algoritmo mostrata in questa pagina.
Quando usarlo e che cosa evitare
Buona scelta quando…
Eccellente per interi con intervallo k non molto più grande di n; è anche il sottoprogramma tipico di radix sort.
Errore comune
Se max−min è enorme rispetto a n, tempo e memoria per i contatori rendono la scelta inefficiente. La simulazione accetta interi non negativi.