Counting sort

Template:Stub informatica

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.

L'algoritmo è semplice ed intuitivo: 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 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.

ordina(A[],min,max) {

  funzione che ordina l'array A contenente valori da min a max
  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]=C[cella]+1;       aumenta il numero di volte che si è incontrato il valore
  }
  inizio=0;  
  per ogni elemento i in C{
       num=C[i];                 legge il numero di volte che si è incontrato il valore
       scrivi(i+min) num volte;  scrive il valore num volte
  }

}