Counting sort
algoritmo di ordinamento
Il Counting sort è un algoritmo di ordinamento con complessità lineare O(n) non basato sul confronto che però ha un prequisito, conoscere l'intervallo dei valori da ordinare.
Il funzionamento è molto semplice. Si crea un vettore C di dimensione pari all'intevallo dei valori da ordinare, ogni indice i del vettore C è utilizzato per contare quanti sono i valori del vettore A da ordinare con valore minore di i. I valori memorizzati in C si utilizzano per sistemare gli elementi di A nella corretta posizione del vettore ordinato.