Counting sort
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 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[]) {
//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++
}
}
}