Counting sort

Questa voce sull'argomento programmazione è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Wikipedia.

Counting sort
Ordinamento di una sequenza numerica tramite il counting sort
Classe	Algoritmo di ordinamento
Struttura dati	Array
Caso peggiore temporalmente	${\displaystyle O(max(n,k))}$
Caso ottimo temporalmente	${\displaystyle O(max(n,k))}$
Caso medio temporalmente	${\displaystyle O(max(n,k))}$
Manuale

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.

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, ${\displaystyle max(A)}$, e minimo, ${\displaystyle min(A)}$, dell'array e si prepara un array ausiliario ${\displaystyle C}$ di lunghezza ${\displaystyle max(A)-min(A)+1}$, che inizialmente contiene solo zeri. ${\displaystyle C}$ conterrà le frequenze di ciascun elemento in ${\displaystyle A}$ (ad esempio ${\displaystyle C[0]=1}$ se ${\displaystyle min(A)}$ appare una sola volta all'interno di ${\displaystyle A}$).

Una volta costruito ${\displaystyle C}$, si visita l'array ${\displaystyle A}$ per popolarlo. Ogni volta che si incontra il valore ${\displaystyle i}$ in ${\displaystyle A}$, si andrà ad aumentare di uno il valore di ${\displaystyle C[i]}$. Al termine di questo processo, ${\displaystyle C[i]}$ sarà pari al numero di occorrenze dell'elemento ${\displaystyle i+min(A)}$ nell'array di partenza ${\displaystyle A}$.

Infine, per ordinare ${\displaystyle A}$, si scorre ${\displaystyle C}$ dalla prima cella all'ultima, scrivendo in ${\displaystyle A}$ il valore ${\displaystyle i+min(A)}$ per ${\displaystyle C[i]}$ volte. Va notato che se un elemento ${\displaystyle k}$ non è presente in ${\displaystyle A}$, allora ${\displaystyle C[k]}$ sarà pari a 0, e dunque quell'elemento non sarà inserito.

${\displaystyle A}$ sarà ordinato alla fine di questo processo perché si è sfruttata la possibilità di accedere prima casualmente e poi sequenzialmente agli indici di ${\displaystyle C}$: scansionare un array significa accedere ai suoi indici in ordine, perciò l'ordinamento è garantito da questa proprietà.

Array A: 2 5 2 7 8 8 2 3 6

Con una scansione di ${\displaystyle A}$ individuo il valore minimo (2) e il valore massimo (8).

Popolo l'array ${\displaystyle C}$, che tiene il conto delle frequenze di ciascun elemento nell'intervallo ${\displaystyle [2,8]}$.

Array C: 3 1 0 1 1 1 2

Il significato dell'array C è il seguente: l'intero 0 ${\displaystyle +min(A)}$ = 2 è presente 3 volte nell'array A, l'intero 1+min(A)=3 è presente 1 volta, l'intero 2+min(A)=4 è presente 0 volte, e così via.

Inserisco in A tre volte l'intero 2, 1 volta l'intero 3, 0 volte l'intero 4, 1 volta l'intero 5 e così via.

Array A: 2 2 2 3 5 6 7 8 8

L'array A è ora ordinato.

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

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

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]
   end for

  //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
   end for

   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
   end for

   //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
   end for

• Thomas Cormen, Charles E. Leiserson, Ronald Rivest, Sorting in Linear Time, in Introduction to Algorithms, 2ª ed., Cambridge, Massachusetts, The MIT Press, 1998, pp. 175-177.
• Thomas Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein, Capitolo 8, Ordinamento in tempo lineare, in Introduzione agli algoritmi e strutture dati, 3ª ed., Cambridge, Massachusetts, McGraw-Hill Education, 2010, pp. 159-161.

• Wikibooks contiene implementazioni del Counting sort

V · D · M Algoritmi di ordinamento
Teoria	Teoria della complessità computazionale · Notazione O Grande · Array · Lista · Stack · Coda · Ordinamento comparativo · Ordinamento adattivo
Algoritmi a scambio	Bubble sort · Shaker sort · Odd-even sort · Comb sort · Gnome sort · Quicksort
Algoritmi di selezione	Selection sort · Heap sort · Smoothsort
Algoritmi ad inserimento	Insertion sort · Shell sort · Tree sort · Library sort · Patience sorting
Algoritmi a fusione	Merge sort · Timsort
Algoritmi non comparativi	Radix sort · Bucket sort · Counting sort · Pigeonhole sort
Altri algoritmi	Rete di ordinamento · Ordinamento topologico · Ordinamento bitonico · Ordinamento delle frittelle
Algoritmi inefficienti	Stupid sort · Trippel sort

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica