Counting sort: differenze tra le versioni

Versione delle 09:41, 28 feb 2008

Versione attuale delle 21:57, 31 gen 2024

(69 versioni intermedie di 40 utenti non mostrate)

Riga 1:

{{S|informaticaprogrammazione}}

{{Algoritmo

|classe = [[Algoritmo di ordinamento]]

|immagine =Counting Sort Animation.gif

|struttura dati = [[Array]]

|tempo = <math>O(max(n,k))</math>

|tempo migliore = <math>O(max(n,k))</math>

|tempo medio = <math>O(max(n,k))</math>

|spazio =

|ottimale =

|didascalia=Ordinamento di una sequenza numerica tramite il counting sort}}

Il '''Counting sort''' è un [[algoritmo di ordinamento]] per valori [[numero intero|numerici interi]] con [[Teoria della complessità computazionale|complessità]] lineare. L'algoritmo si basa sulla conoscenza a priori dell'[[Intervallo (matematica)|intervallo]] in cui sono compresi i valori da ordinare.

== Descrizione intuitiva ==

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

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).

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

==Pseudocodice==

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

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

== Esempio ==

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

=== Prima scansione ===

Con una scansione di <math>A</math> individuo il valore minimo (2) e il valore massimo (8).

=== Seconda scansione ===

Popolo l'array <math>C</math>, che tiene il conto delle frequenze di ciascun elemento nell'intervallo <math>[2,8]</math>.

Array C: 3 1 0 1 1 1 2

Il significato dell'array C è il seguente: l'intero 0 <math>+min(A)</math> = 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.

=== Terza scansione ===

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.

== Complessità ==

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

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

==Pseudocodice==

countingSort(A[])

//CacoloCalcolo degli elementi max e min

max ← A[0]

min ← A[0]

Riga 16 ⟶ 54:

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

Riga 29 ⟶ 73:

k ← k + 1

C[i] ← C[i] - 1

end for

==Implementazioni Bibliografia ==

* {{cita libro| Thomas | Cormen | Introduction to Algorithms | 1998| The MIT Press | Cambridge, Massachusetts | coautori=Charles E. Leiserson, [[Ronald Rivest]]| capitolo=Sorting in Linear Time | ed=2 |pp=175-177}}

===[[C (linguaggio)|C]]===

*{{cita libro|Thomas|Cormen|Introduzione agli algoritmi e strutture dati|2010|McGraw-Hill Education|Cambridge, Massachusetts|coautori=Charles E. Leiserson, [[Ronald Rivest]], Clifford Stein|capitolo=Capitolo 8, Ordinamento in tempo lineare|ed=3|pp=159-161}}

<source lang="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]]--;

}

}

</source>

== Altri progetti ==

===[[C++]]===

{{interprogetto|b=Implementazioni di algoritmi/Counting sort|b_oggetto=implementazioni|b_preposizione=del|preposizione=sul}}

<source lang="cpp">

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;

}

</source>

===[[Java]]===

<source lang="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]--;

}

}

}

</source>

{{Ordinamento}}

{{Portale|informatica}}

[[Categoria:Algoritmi di ordinamento]]

[[Categoria:Algoritmi di ordinamento]]

[[cs:Counting sort]]

[[de:Countingsort]]

[[en:Counting sort]]

[[es:Ordenamiento por cuentas]]

[[fi:Laskentalajittelu]]

[[fr:Tri comptage]]

[[he:מיון מנייה]]

[[nl:Counting sort]]

[[pl:Sortowanie przez zliczanie]]

[[pt:Counting sort]]

[[ru:Сортировка подсчётом]]

[[uk:Сортування підрахунком]]