Implementazioni di algoritmi/Bucket sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
|||
Riga 4:
L'algoritmo è semplice ed intuitivo: si prepara un array C di dimensione pari a m (cioè al valore massimo che può essere nell'array) con C[i] che rappresenta la frequenza dell'elemento i 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.
==Spiegazione Astratta==
L'algoritmo come detto in precedenza usa un [[array|vettore]] ausiliario( da ora in poi ''Y'') dove la t-esima cella contiene la frequenza dell'elemento t nel [[array|vettore]] di input ( da ora in poi ''X'').
Per fare un esempio, se ''X'' fosse cosi strutturato:
'''posizione''' 1 2 3 4 5 6 7 8 9
'''elemento''' 10 2 8 3 2 4 4 1 5
''Y'' sarebbe:
'''posizione''' 1 2 3 4 5 6 7 8 9 10
'''elemento''' 1 2 1 2 1 0 0 1 0 1
Una volta costruito ''Y'' con le frequenze di ogni elemento di ''X'' si può ricostruire il [[array|vettore]] ordinato, analizzando ''Y'' dalla prima cella:
#Se Y[k]=0 passa alla cella successiva di Y.
#Se Y[k]=c>0 aggiungi c volte il valore k in ''X''.
==Pseudo-codice==
IntegerSort(array X, intero M)
sia Y un array di dimensione m //Dichiarazione della struttura di appoggio
for i ← 1 to m do
Y[i] ← 0 //Inizializzazione del vettore Y
for i ← 1 to n do
Y[X[i]] ← Y[X[i]] + 1 //Costruzione del vettore delle frequenze
j ← 1
for i ← 1 to m do
for z ← 1 to Y[i] do //Ricostruzione del vettore di X sulla base di Y
X[j] ← i
j ← j + 1
==Analisi dell'algoritmo==
La complessità del Bucket Sort è ''O(n + m)'' infatti infatti la [[Teoria_della_complessit%C3%A0_algoritmica|complessità]] per inizializzare il vettore Y e leggerlo per ricostruire X è ''O(m)'', mentre la [[Teoria_della_complessit%C3%A0_algoritmica|complessità]] del terzo ciclo for è ''O(n)''.
Da questo possiamo capire l'utilità del Bucket Sort: infatti se m = ''O(n)'' allora la [[Teoria_della_complessit%C3%A0_algoritmica|complessità]] totale dell'algoritmo è ''O(n)''.
==Implementazioni==
| |||