Counting sort: differenze tra le versioni

Versione delle 00:54, 18 mag 2009

Versione attuale delle 21:57, 31 gen 2024

(55 versioni intermedie di 34 utenti non mostrate)

Riga 1:

{{S|informaticaprogrammazione}}

{{Infobox Algoritmo

|classclasse = [[Algoritmo di ordinamento]]

|immagine =Counting Sort Animation.gif

|image=

|datastruttura dati = [[Array]]

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

|best-timetempo migliore = <math>O(max(n + ,k))</math>

|average-timetempo medio = <math>O(max(n + ,k))</math>

|spazio =

|space=

|ottimale =

|optimal=

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

Riga 15:

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 dimensionelunghezza pari<math>max(A) all'intervallo- deimin(A) valori+ con C[i]1</math>, che rappresentainizialmente lacontiene frequenzasolo dell'elementozeri. <math>i+min(A)C</math> nell'arrayconterrà dile partenzafrequenze A.di Siciascun visitaelemento l'arrayin <math>A</math> aumentando(ad l'elemento diesempio <math>C[0] corrispondente.= Dopo1 si</math> visitase l'array<math>min(A)</math> Cappare inuna ordinesola evolta siall'interno scrivono su A, C[i] copie del valoredi <math>i+min(A)</math>).

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

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 duetre [[iterazione|iterazioni]], unadue di lunghezza <math>n</math> per(pari ilalla calcololunghezza delledell'array occorrenzeda dei valori e una di lunghezza <math>m</math>ordinare) per la l'impostazioneindividuazione delle posizioni finali dei valori. La [[O-grande|complessità]] totale è quindidi <math>Omax(n+mA)</math>, dovee <math>nmin(A)</math> èe laper lunghezzail dell'arraycalcolo dadelle ordinareoccorrenze dei valori, e una di lunghezza <math>mk</math> è (pari a <math>max(A)-min(A)+1</math> (<math>max(A)</math> e <math>min(A)</math> sono rispettivamenteper l'elementoimpostazione piùdelle grandeposizioni efinali l'elementodei piùvalori: piccolola dell'array)[[O-grande|complessità]] ovverototale è ilquindi range dei valori contenuti nell'array<math>O(n+k)</math>.

Non è basato su confronti e scambi e conviene utilizzarlo quando il valore di m<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[])

//Calcolo degli elementi max e min

Riga 33 ⟶ 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 46 ⟶ 73:

k ← k + 1

C[i] ← C[i] - 1

end for

== Bibliografia ==

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

*{{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}}

== Altri progetti ==

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

{{Ordinamento}}

{{Portale|informatica}}

[[Categoria:Algoritmi di ordinamento]]

[[Categoria:Algoritmi di ordinamento]]

[[cs:Counting sort]]

[[de:Countingsort]]

[[en:Counting sort]]

[[es:Ordenamiento por cuentas]]

[[fa:مرتب‌سازی شمارشی]]

[[fi:Laskentalajittelu]]

[[fr:Tri comptage]]

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

[[nl:Counting sort]]

[[pl:Sortowanie przez zliczanie]]

[[pt:Counting sort]]

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

[[tr:Sayarak sıralama]]

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