Counting sort: differenze tra le versioni

Versione delle 19:08, 26 mar 2018

Versione delle 19:16, 26 mar 2018

Riga 15:

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.

Si calcolano i valori massimo, <math>max(A)</math>, e minimo, <math>min(A)</math>, dell'array e si prepara un array ausiliario <math>C</math> di dimensione pari all'intervallo dei valori con <math>C[i]</math>che rappresenta la frequenza dell'elemento <math>i+min(A)</math> nell'array di partenza <math>A</math>. Si visita l'array <math>A</math> aumentando l'elemento di <math>C</math> corrispondente. Dopo si visita l'array <math>C</math> in ordine e si scrivono su <math>A</math>, <math>C[i]</math>copie del valore <math>i+min(A)</math>.

== Complessità ==

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==