Vai al contenuto principale
← OlimpiApp Facile

Informatica · Ordinamento

Counting sort: vettore dei conteggi cumulativi

Counting sort ordina l'array
3, 1, 4, 1, 5, 0, 3, 2, 5, 1, 3, 0
con valori in $\{0, 1, 2, 3, 4, 5\}$. Prima conta le occorrenze di ogni valore, poi calcola le somme prefisse ottenendo il vettore C dove C[v] è il numero di elementi con valore $\le v$ (C[v] indica la posizione finale dell'ultima copia di v nell'array ordinato).

Qual è il vettore (C[0], C[1], C[2], C[3], C[4], C[5])?