Bucket sort

Questa voce sull'argomento programmazione è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Wikipedia.

Bucket sort
Classe	Algoritmo di ordinamento
Struttura dati	Array
Caso peggiore temporalmente	${\displaystyle O(n)}$
Ottimale	?
Manuale

Il bucket sort è un algoritmo di ordinamento per valori numerici che si assume siano distribuiti uniformemente in un intervallo ${\displaystyle [0,1)}$. La complessità del bucket sort è lineare O(n).

Spiegazione astratta

Se n è il numero di elementi da ordinare, l'intervallo ${\displaystyle [0,1)}$ è diviso in n intervalli di uguale lunghezza, 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.

Pseudo-codice

 BucketSort(array A, intero N)
   for i ← 1 to length[A] do
     // restituisce un indice di bucket per l'elemento A[i]
     bucket ← f(A[i], N)
     // inserisce l'elemento A[i] nel bucket corrispondente
     aggiungi(A[i], B[bucket])
   for i ← 1 to N do
     // ordina il bucket
     ordina(B[i])
   // restituisce la concatenazione dei bucket
   return concatena(B)

N è 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à

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^[1], utilizzando insertion sort l'ordinamento di ogni bucket è dell'ordine di ${\displaystyle \Theta (1)}$, quindi la complessità media di O(n) per tutto l'algoritmo. La complessità nel caso migliore è lineare, O(n+m) dove m è il massimo valore nell'array.

Note

Bibliografia

• (EN) Thomas Cormen, Charles E. Leiserson e Ronald Rivest, Sorting in Linear Time, in Introduction to Algorithms, 2ª ed., Cambridge, Massachusetts, The MIT Press, 1998, pp. 180-182, ISBN 0-262-53091-0.

Altri progetti

• Wikibooks contiene implementazioni di Bucket sort
• Wikimedia Commons contiene immagini o altri file sul Bucket sort

V · D · M Algoritmi di ordinamento
Teoria	Teoria della complessità computazionale · Notazione O Grande · Array · Lista · Stack · Coda · Ordinamento comparativo · Ordinamento adattivo
Algoritmi a scambio	Bubble sort · Shaker sort · Odd-even sort · Comb sort · Gnome sort · Quicksort
Algoritmi di selezione	Selection sort · Heap sort · Smoothsort
Algoritmi ad inserimento	Insertion sort · Shell sort · Tree sort · Library sort · Patience sorting
Algoritmi a fusione	Merge sort · Timsort
Algoritmi non comparativi	Radix sort · Bucket sort · Counting sort · Pigeonhole sort
Altri algoritmi	Rete di ordinamento · Ordinamento topologico · Ordinamento bitonico · Ordinamento delle frittelle
Algoritmi inefficienti	Stupid sort · Trippel sort

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