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
      while C[i] > 0 do                        //scrive C[i] volte il valore (i + min) nell'array A
         A[k] ← i + min
         k ← k + 1
         C[i] ← C[i] - 1

Implementazioni

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<=M;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]]--;
    }
 }

C++

void counting_sort(int *nums, int size)
{
	//Cerca i valori minimi e massimi nell'array
	int i, min = nums[0], max = min;
	for(i = 1; i < size; ++i)
	{
		if (nums[i] < min)
			min = nums[i];
		else if (nums[i] > max)
			max = nums[i];
	}
	
	//Crea un array per contare (come nel bucket sort)
	int distinct_element_count = max - min + 1;
	int* counts = new int[distinct_element_count];
	for(i=0; i<distinct_element_count; ++i)
		counts[i] = 0;
	
	//Per ogni valore nell'array da ordinare
	//aumenta di 1 il corrispondente elemento nell'array di conteggio
	//(Esattamente come nel bucket sort)
	for(i=0; i<size; ++i)
		++counts[ nums[i] - min ];
	
	//Inserisce nell'array principale i valori contati
	int j=0;
	for(i=min; i<=max; i++)
		for(int z=0; z<counts[i-min]; z++)
			nums[j++] = i;
}

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