Counting sort

Template:Infobox Algoritmo Il Counting sort è un algoritmo di ordinamento per valori numerici interi con complessità lineare. L'algoritmo si basa sulla conoscenza a priori dell'intervallo in cui sono compresi i valori da ordinare.

Descrizione intuitiva

L'algoritmo conta il numero di occorrenze di ciascun valore presente nell'array da ordinare, memorizzando questa informazione in un array temporaneo di dimensione pari all'intervallo di valori. Il numero di ripetizioni dei valori inferiori indica la posizione del valore immediatamente successivo.

Si calcolano i valori massimo, $max(A)$, e minimo, $min(A)$, dell'array e si prepara un array ausiliario 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)$.

Complessità

L'algoritmo esegue tre iterazioni, due di lunghezza $n$ (pari alla lunghezza dell'array da ordinare) per l'individuazione di $max(A)$ e $min(A)$ e per il calcolo delle occorrenze dei valori, e una di lunghezza $k$ (pari a $max(A)-min(A)+1$) per l'impostazione delle posizioni finali dei valori: la complessità totale è quindi $O(n+k)$.

Non è basato su confronti e scambi e conviene utilizzarlo quando il valore di k è $O(n)$, nel qual caso l'algoritmo è $O(n)$, altrimenti risulterebbero più veloci altri algoritmi.

Pseudocodice

countingSort(A[])
   //Calcolo 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

Esempio in Java

public class NonComparative {

	public static int[] countingSorting(int[] array){
		int i;
		
		int min, max;
		max = min = array[0];
		
		for(i=1; i<array.length; i++)
		{
			if (array[i] > max)
			    max = array[i];
			else 
                            if(array[i] < min)
				min = array[i];
		}
		
		int length = max - min +1;
		
		
		int[] suppArray = new int[length];
		int[] returnArray = new int[length];
		
		//aumenta il numero di volte che si è incontrato il valore
		for(i=0; i<array.length; i++)
			suppArray[array[i]] += 1;
		
		//numero di elementi <= i
		for(i=1; i<suppArray.length; i++)
			suppArray[i] += suppArray[i-1];
				
		for(i=array.length-1; i>=0; i--)
		{
			returnArray[suppArray[array[i]]-1] = array[i];
			suppArray[array[i]] -= 1; 
		}
		
		return returnArray;
	}
}

Bibliografia

• Thomas Cormen, Charles E. Leiserson, Ronald Rivest, Sorting in Linear Time, in Introduction to Algorithms, 20ª ed., Cambridge, Massachussetts, The MIT Press, 1998, pp. 175-177.

Altri progetti

Altri progetti

• Wikibooks

• Wikibooks contiene implementazioni di Counting sort