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 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 scrivono su A, C[i] copie del valore i+min(A).

Pseudocodice

countingSort(A[])
   //Cacolo degli elementi max e min
   max ← A[0]
   min ← A[0]
   for i ← 1 to length[A] do
      if (A[i] > max) then
         max ← A[i]
      else if(A[i] < min) then
         min ← A[i]
   //Costruzione dell'array C
   * crea un array C di dimensione max - min + 1
   for i ← 0 to length[C] do
      C[i] ← 0                                 //inizializza a zero gli elementi di C
   for i ← 0 to length[A] do
      C[A[i] - min] = C[A[i] - min] + 1            //aumenta il numero di volte che si è incontrato il valore
   //Ordinamento in base al contenuto dell'array delle frequenze C
   k ← 0                                       //indice per l'array A
   for i ← 0 to length[C] do
      valore ← i + min
      while C[i] > 0 do                        //scrive C[i] volte il valore nell'array A
         A[k] ← i + min
         k ← k + 1
         C[i] ← C[i] - 1

Implementazioni

Algoritmo in 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<dim;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]]--;
   }
}

Algoritmo in C++

void countingSort(int* A, int lengthA)
{  
   //Cacolo degli elementi max e min
   int max=A[0];
   int min=A[0];
   int i=1;
   for(; i<lengthA; i++){
      if(A[i]>max) max=A[i];
      else if(A[i]<min) min=A[i];
   }
   //Costruzione dell'array C
   int lengthC=max-min+1;
   int C[lengthC];                      //crea l'array C
   for(i=0; i<lengthC; i++) C[i]=0;     //inizializza a zero gli elementi di C
   for(i=0; i<lengthA; 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<lengthC; i++){
      int valore=i+min;
      while(C[i]>0){                     //scrive C[i] volte il valore nell'array A
         A[k]=i+min;
         K++;
         C[i]--;
      }
   }
}

Algoritmo in 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++){
      int valore=i+min;
      while(C[i]>0){                     //scrive C[i] volte il valore nell'array A
         A[k]=i+min;
         K++;
         C[i]--;
      }
   }
}