Counting sort: differenze tra le versioni

Versione delle 16:41, 29 mar 2023

Versione attuale delle 21:57, 31 gen 2024

(6 versioni intermedie di 5 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>

Riga 9:

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

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

Riga 63:

for i ← 0 to length[A] do

C[A[i] - min] = C[A[i] - min] + 1 -3 //aumenta il numero di volte che si è incontrato il valore

end for