Bucket sort

Da Wikipedia, l'enciclopedia libera.
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.

Spiegazione astratta[modifica | modifica sorgente]

La prima parte dell'algoritmo: divisione nei bucket.

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.

Seconda parte dell'algoritmo: ordinamento dei bucket e concatenazione.

Pseudo-codice[modifica | modifica sorgente]

 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.

Complessità[modifica | modifica sorgente]

La complessità del bucket sort è O(n) per tutti i cicli, a parte 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.

Bibliografia[modifica | modifica sorgente]

  • Thomas Cormen, Charles E. Leiserson, Ronald Rivest, Sorting in Linear Time in Introduction to Algorithms, 2ª ed., Cambridge, Massachussetts, The MIT Press, 1998, pp. 180-182.

Altri progetti[modifica | modifica sorgente]

informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica