Counting sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
LiveRC : Annullata la modifica di 192.167.9.178; ritorno alla versione di Baruneju |
mNessun oggetto della modifica |
||
Riga 1:
{{S|informatica}}
{{Infobox Algoritmo
|class=[[Algoritmo di ordinamento]]
|image=
|data=[[Array]]
|time=<math>O(n + k)</math>
|best-time=<math>O(n + k)</math>
|average-time=<math>O(n + k)</math>
|space=
|optimal=
}}
Il '''Counting sort''' è un [[algoritmo di ordinamento]] per valori [[numero intero|numerici interi]] con [[Teoria della complessità computazionale|complessità]] lineare. L'algoritmo si basa sulla conoscenza a priori dell'[[Intervallo (matematica)|intervallo]] in cui sono compresi i valori da ordinare.
== Descrizione intuitiva ==
L'algoritmo conta il numero di occorrenze di ciascun valore presente nell'[[array]] da ordinare, memorizzando questa informazione in un array temporaneo di dimensione pari all'intervallo di valori. Il numero di ripetizioni dei valori inferiori indica la posizione del valore immediatamente successivo.
| |||