Counting sort: differenze tra le versioni

Versione delle 23:02, 21 gen 2006

Versione delle 23:19, 21 gen 2006

Riga 5:

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).

'''Algoritmo in C'''

countingSort(A[])

void countingSort(int A[], int lengthA)

{

//Cacolo degli elementi max e min

int max=A[0];

int min=A[10];

per ogni elementoint i in A{=1;

for(; i<lengthA; se A[i]>max++){

alloraif(A[i]>max) max=A[i];

altrimenti seelse if(A[i]<min) min=A[i];

allora min=A[i];

}

//Costruzione dell'array C

creaarrayint C[lengthC=max-min+1]; //crea un array C

int valore=AC[ilengthC]; //legge il valore nell //crea l'array C

per ogni elemento i in A{

for(i=0; i<lengthC; i++) C[i]=0; //inizializza a zero gli elementi di C

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

for(i=0; i<lengthA; i++)

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

C[cellaA[i]-min]++; //aumenta il numero di volte che si è incontrato il valore

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

int k=0; //indice per l'array A

for(i=0; i<lengthC; i++){

finchè while(C[i]>0){ //scrive C[i] volte il valore numi+min nell'array A

A[k++]=numi+min;

k++}

}

}

'''Algoritmo in Java'''

void countingSort(int A[])

{

//Cacolo degli elementi max e min

int max=A[0];

alloraint min=A[i0];

int i=1;

for(; i<A.length; i++){

if(A[i]>max) max=A[i];

else if(A[i]<min) min=A[i];

}

//Costruzione dell'array C

int C[]=new int[max-min+]; //crea l'array C

for(i=0; i<A.length; i++)

C[A[i]-min]++; //aumenta il numero di volte che si è incontrato il valore

for(i=0; i<C.length; i++) C[i]=0; //inizializza a zero gli elementi di C

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

int k=0; //indice per l'array A

perfor(i=0; ogni elementoi<C.length; i in C++){

while(C[i]>0){ //scrive C[i] volte il valore i+min nell'array A

num=i+min

num A[k++]=i+min;

finchè C[i]>0{ //scrive C[i] volte il valore num nell'array A

A[k]=num;

k++

}

}

}