Counting sort: differenze tra le versioni

Versione delle 10:13, 13 nov 2005

Versione delle 16:11, 21 gen 2006

Riga 1:

{{stub informatica}}

Il '''Counting sort''' è un [[algoritmo]] di ordinamento per valori numerici interi con [[complessità]] lineare O(n+m), nondove basaton sulè confrontola chelunghezza peròdell'array hae unm prequisito,è conoscerepari a max(A)-min(A)+1 (max(A) e min(A) sono rispettivamenti l'intervalloelemento più grande e l'elemento più piccolo dell'array) ovvero è il range dei valori dacontenuti 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 ordinarealgoritmi.

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 (l'[[algoritmo]] non agisce infatti in loco) con C[i] che rappresenta la frequenza dell'elemento i+min 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 stampano, per ogni elemento i, C[i] copie.

countingSort(A[])

ordina(A[],min,max)

{

//Cacolo degli elementi max e min

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

max=A[0];

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

min=A[1];

per ogni elemento i in A{

se A[i]>max

allora max=A[i];

altrimenti se A[i]<min

allora min=A[i];

}

//costruzione dell'array C

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

}

//Ordinamento in base al contenuto dell'array delle fraquenze C

inizio=0;

k=0 //indice per l'array A

per ogni elemento i in C{

num=i+min

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

finchè scrivi(C[i+min)]>0{ num volte; //scrive C[i] volte il valore num voltenell'array A

A[k]=num;

k++

}

}

}