Counting sort: differenze tra le versioni

Versione delle 16:56, 21 giu 2021

Versione delle 00:56, 24 gen 2023

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)</math>, nell'arrayche diinizialmente partenzacontiene solo 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= ordine1 e si scrivono su <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à ==