|
C[i] ← C[i] - 1
== Altri progetti ==
==Implementazioni==
{{interprogetto|b=Algoritmi/Counting sort|b_oggetto=implementazioni|b_preposizione=di}}
{{Trasferimento|wb|Implementazioni}}
===[[C (linguaggio)|C]]===
<source lang="C">
void countingSort(int v[], int dim, int ris[])
{
int i, occ[M+1];
for(i=0;i<=M;i++) //Inizializza array per le occorrenze
occ[i]=0;
for(i=0;i<dim;i++) // Inserisce nell'array occ il numero di occorrenze
occ[v[i]]++;
for(i=1;i<=M;i++) // occ[i] contiene il numero di elementi <=i in v
occ[i]+=occ[i-1];
for(i=dim-1;i>=0;i--) { // Dispone gli elementi di v in ris
ris[occ[v[i]]-1]=v[i];
occ[v[i]]--;
}
}
</source>
===[[C++]]===
<source lang="cpp">
void counting_sort(int *nums, int size)
{
//Cerca i valori minimi e massimi nell'array
int i, min = nums[0], max = min;
for(i = 1; i < size; ++i)
{
if (nums[i] < min)
min = nums[i];
else if (nums[i] > max)
max = nums[i];
}
//Crea un array per contare (come nel bucket sort)
int distinct_element_count = max - min + 1;
int* counts = new int[distinct_element_count];
for(i=0; i<distinct_element_count; ++i)
counts[i] = 0;
//Per ogni valore nell'array da ordinare
//aumenta di 1 il corrispondente elemento nell'array di conteggio
//(Esattamente come nel bucket sort)
for(i=0; i<size; ++i)
++counts[ nums[i] - min ];
//Inserisce nell'array principale i valori contati
int j=0;
for(i=min; i<=max; i++)
for(int z=0; z<counts[i-min]; z++)
nums[j++] = i;
}
</source>
===[[Java]]===
<source lang="java">
void countingSort(int[] A)
{
//Cacolo degli elementi max e min
int max=A[0];
int min=A[0];
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+1]; //crea l'array C
for(i=0; i<C.length; i++) C[i]=0; //inizializza a zero gli elementi di C
for(i=0; i<A.length; i++)
C[A[i]-min]++; //aumenta il numero di volte che si è incontrato il valore
//Ordinamento in base al contenuto dell'array delle frequenze C
int k=0; //indice per l'array A
for(i=0; i<C.length; i++){
while(C[i]>0){ //scrive C[i] volte il valore (i+min) nell'array A
A[k]=i+min;
k++;
C[i]--;
}
}
}
</source>
{{Ordinamento}}
| 