Bucket sort
| Classe | Algoritmo di ordinamento |
|---|---|
| Struttura dati | Array |
| Caso peggiore temporalmente | O(nlogn) |
| Ottimale | ? |
Il Bucket sort è un algoritmo di ordinamento per valori numerici che si assume siano distribuiti uniformemente in un intervallo semichiuso [0,1). La complessità del bucket sort è lineare O(n+m) (ove m è il valore max nell'array), questo è possibile in quanto l'algoritmo non è basato su confronti.
Indice |
[modifica] Spiegazione astratta
L'intervallo dei valori, noto a priori, è diviso in intervalli più piccoli, detti bucket (cesto). Ciascun valore dell'array è quindi inserito nel bucket a cui appartiene, i valori all'interno di ogni bucket vengono ordinati e l'algoritmo si conclude con la concatenazione dei valori contenuti nei bucket.
[modifica] Pseudo-codice
BucketSort(array A, intero M)
for i ← 1 to length[A] do
// restituisce un indice di bucket per l'elemento A[i]
bucket ← f(A[i], M)
// inserisce l'elemento A[i] nel bucket corrispondente
aggiungi(A[i], B[bucket])
for i ← 1 to M do
// ordina il bucket
ordina(B[i])
// restituisce la concatenazione dei bucket
return concatena(B)
M è il numero di bucket da usare, la funzione f calcola il bucket in cui inserire l'elemento, ordina è un algoritmo di ordinamento e concatena restituisce un array composto dalla concatenazione dei valori dei bucket.
[modifica] Complessità
La complessità del bucket sort è O(n) per tutti i cicli, a parte il l'ordinamento dei singoli bucket. Date le premesse sull'input, come descritto in Introduction to Algorithms, pp. 182, utilizzando insertion sort l'ordinamento di ogni bucket è dell'ordine di Θ(1), quindi la complessità totale è O(n) per tutto l'algoritmo.
[modifica] Bibliografia
- Thomas Cormen; Charles E. Leiserson, Ronald Rivest, Sorting in Linear Time in Introduction to Algorithms , 2a ed., Cambridge, Massachussetts, The MIT Press, 1998, pp. 180-182.
[modifica] Altri progetti
Wikibooks contiene implementazioni di Bucket sort
 Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica |
