Implementazioni di algoritmi/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).

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;
         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;
         C[i]--;
      }
   }
}