Counting sort: differenze tra le versioni

Versione delle 09:19, 24 set 2018

Versione attuale delle 21:57, 31 gen 2024

(14 versioni intermedie di 10 utenti non mostrate)

Riga 2:

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

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 dimensione pari all'intervallo dei valori conlunghezza <math>C[i]</math>chemax(A) rappresenta- la frequenza dell'elemento <math>i+min(A) + 1</math>, nell'arrayche diinizialmente contiene partenzasolo zeri. <math>AC</math>. Siconterrà visitale l'arrayfrequenze <math>A</math>di aumentandociascun l'elemento diin <math>CA</math> corrispondente.(ad Dopo si visita l'arrayesempio <math>C</math>[0] in ordine e si scrivono su= 1 <math>A</math>, se <math>C[i]min(A)</math>copie delappare valoreuna sola volta all'interno di <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à ==

Riga 41 ⟶ 63:

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

Riga 51 ⟶ 73:

k ← k + 1

C[i] ← C[i] - 1

end for

== 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}}

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