Bucket sort
Bucket sort | |
---|---|
Classe | Algoritmo di ordinamento |
Struttura dati | Array |
Caso peggiore temporalmente | |
Ottimale | ? |
Manuale |
Il bucket sort è un algoritmo di ordinamento per valori numerici che si assume siano distribuiti uniformemente in un intervallo . La complessità del bucket sort è lineare O(n).
Spiegazione astratta
Se n è il numero di elementi da ordinare, l'intervallo è 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 , 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
- ^ Cormen, pag. 182.
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
Altri progetti
- Wikibooks
- Wikimedia Commons
- Wikibooks contiene implementazioni di Bucket sort
- Wikimedia Commons contiene immagini o altri file sul Bucket sort
V · D · M | ||
---|---|---|
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 |