Counting sort: differenze tra le versioni

Versione delle 16:14, 21 gen 2006

Versione delle 23:02, 21 gen 2006

Riga 3:

Il '''Counting sort''' è un [[algoritmo]] di ordinamento per valori numerici interi con [[complessità]] lineare O(n+m), dove n è la lunghezza dell'array e m è pari a max(A)-min(A)+1 (max(A) e min(A) sono rispettivamenti 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.

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(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 stampano,scrivono persu ogni elemento iA, C[i] copie del valore i+min(A).

countingSort(A[])

{

//Cacolo degli elementi max e min

max=A[0];

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]++; //aumenta il numero di volte che si è incontrato il valore

}

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

k=0 //indice per l'array A

per ogni elemento i in C{

num=i+min

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

A[k]=num;

k++

}

}

}