Counting sort: differenze tra le versioni

Versione delle 22:38, 3 set 2005

Versione delle 10:05, 15 set 2005

Riga 3:

Il '''Counting sort''' è un [[algoritmo]] di ordinamento con [[complessità]] lineare O(n) non basato sul confronto che però ha un prequisito, conoscere l'intervallo dei valori da ordinare.

Il funzionamentoL'algoritmo è molto semplice. Sied intuitivo: si creaprepara un vettorearray C di dimensione pari all'intevallointervallo dei valori da(l'[[algoritmo]] ordinare,non ogniagisce indiceinfatti ''i''in delloco) vettorecon C[i] èche utilizzatorappresenta perla contarefrequenza quanti sonodell'elemento i valorinell'array deldi vettorepartenza A. daSi ordinarevisita conl'array valoreA minore diaumentando l''i''.elemento Idi valoriC memorizzaticorrispondente. in CDopo si utilizzanovisita perl'array sistemareC gliin elementiordine die Asi nellastampano, correttaper posizioneogni delelemento vettorei, C[i] ordinatocopie.

ordina(A[],min,max)

{

funzione che ordina l'array A contenente valori da min a max

creaarray C[max-min+1]; crea un array C

per ogni elemento i in A{

valore=A[i]; legge il valore nell'array

cella=valore-min; calcola la cella in C corrispondente al valore

C[cella]=C[cella]+1; aumenta il numero di volte che si è incontrato il valore

}

inizio=0;

per ogni elemento i in C{

num=C[i]; legge il numero di volte che si è incontrato il valore

scrivi(i+min) num volte; scrive il valore num volte

}

}

[[Categoria:Algoritmi di ordinamento]]