Counting sort: differenze tra le versioni

Versione delle 14:50, 26 mar 2008

Versione delle 15:14, 26 mar 2008

Riga 1:

{{S|informatica}}

{{WIP|Baruneju}}

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.

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

== Complessità ==

L'algoritmo esegue due [[iterazione|iterazioni]], una di lunghezza <math>n</math> per il calcolo delle occorrenze dei valori e una di lunghezza <math>m</math> per la l'impostazione delle posizioni finali dei valori. La [[O-grande|complessità]] totale è quindi <math>O(n+m)</math>, dove <math>n</math> è la lunghezza dell'array da ordinare e <math>m</math> è pari a <math>max(A)-min(A)+1</math> (<math>max(A)</math> e <math>min(A)</math> sono rispettivamentirispettivamente l'elemento più grande e l'elemento più piccolo dell'array) ovvero è il range dei valori contenuti nell'array. Non è basato su confronti e scambi e conviene utilizzarlo quando il valore di m è piccolo rispetto a n, altrimenti risulterebbero più veloci altri algoritmi.

Non è basato su confronti e scambi e conviene utilizzarlo quando il valore di m è <math>O(n)</math>, nel qual caso l'algoritmo è <math>O(n)</math>, altrimenti risulterebbero più veloci altri algoritmi.

L'algoritmo è semplice ed intuitivo: si calcolano i valori max(A) e min (A) e si prepara un array C di dimensione pari all'intervallo dei valori con C[i] che rappresenta la frequenza dell'elemento i+min(A) nell'array di partenza A. Si visita l'array A aumentando l'elemento di C corrispondente. Dopo si visita l'array C in ordine e si scrivono su A, C[i] copie del valore i+min(A).

==Pseudocodice==