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

Altri progetti

Wikibooks contiene implementazioni di Counting sort