Occorre comunque leggere n elementi e inizializzare k contatori: Θ(n+k).
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. Le somme cumulative dicono l’ultima posizione di ogni chiave; attraversando l’input da destra si costruisce un output stabile.
Invariante: Dopo le somme cumulative, C[v] è il numero di elementi ≤ v. Durante la costruzione indica la prossima posizione libera per v.
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à
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.