Counting sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Etichette: Annullato Modifica da mobile Modifica da web per mobile |
Aggiunto un'immagine relativa all'ordinamento di una sequenza numerica tramite il counting sort e la relativa didascalia nel template "Algoritmo" |
||
| (2 versioni intermedie di uno stesso utente non sono mostrate) | |||
Riga 2:
{{Algoritmo
|classe = [[Algoritmo di ordinamento]]
|immagine =Counting Sort Animation.gif
|struttura dati = [[Array]]
|tempo = <math>O(max(n,k))</math>
Riga 9:
|spazio =
|ottimale =
|didascalia=Ordinamento di una sequenza numerica tramite il counting sort}}
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.
Riga 42:
L'algoritmo esegue tre [[iterazione|iterazioni]], due di lunghezza <math>n</math> (pari alla lunghezza dell'array da ordinare) per l'individuazione di <math>max(A)</math> e <math>min(A)</math> e per il calcolo delle occorrenze dei valori, e una di lunghezza <math>k</math> (pari a <math>max(A)-min(A)+1</math>) per l'impostazione delle posizioni finali dei valori: la [[O-grande|complessità]] totale è quindi <math>O(n+k)</math>.
Non è basato su confronti e scambi e conviene utilizzarlo quando il valore di <math>k</math> è <math>O(n)</math>, nel qual caso l'algoritmo è <math>O(n)</math>, altrimenti risulterebbero più veloci altri algoritmi.
==Pseudocodice==
| |||