# Implementazioni di algoritmi/Bucket sort

Implementazioni di algoritmi
Copertina Tutti i moduli · Sviluppo
    CopertinaImplementazioni di algoritmi/Copertina
* Algoritmo di EuclideImplementazioni di algoritmi/Algoritmo di Euclide
* Elevazione a potenzaImplementazioni di algoritmi/Elevazione a potenza
* Prodotto scalareImplementazioni di algoritmi/Prodotto scalare
* Calcolo della PasquaImplementazioni di algoritmi/Calcolo della Pasqua
* Metodo Monte CarloImplementazioni di algoritmi/Metodo Monte Carlo
* Ricerca
** Ricerca dicotomicaImplementazioni di algoritmi/Ricerca dicotomica
* Numeri primi
** Crivello di EratosteneImplementazioni di algoritmi/Crivello di Eratostene
** Test di primalità
*** Test deterministicoImplementazioni di algoritmi/Test deterministico
*** Test di Miller-RabinImplementazioni di algoritmi/Test di Miller-Rabin
* PRNG
** Mersenne TwisterImplementazioni di algoritmi/Mersenne Twister
** Test Chi QuadratoImplementazioni di algoritmi/Test Chi Quadrato
* Crittografia
** RSAImplementazioni di algoritmi/RSA
** TEAImplementazioni di algoritmi/TEA
* π(Metodi per definire il pi greco)
** Pi grecoImplementazioni di algoritmi/Pi greco
* Algoritmi di ordinamento
** Bubble sortImplementazioni di algoritmi/Bubble sort
** Bucket sortImplementazioni di algoritmi/Bucket sort
** Counting sortImplementazioni di algoritmi/Counting sort
** Gnome sortImplementazioni di algoritmi/Gnome sort
** Insertion sortImplementazioni di algoritmi/Insertion sort
** Merge sortImplementazioni di algoritmi/Merge sort
** QuicksortImplementazioni di algoritmi/Quicksort
** Radix sortImplementazioni di algoritmi/Radix sort
** Selection sortImplementazioni di algoritmi/Selection sort
** Shaker sortImplementazioni di algoritmi/Shaker sort
** Shell sortImplementazioni di algoritmi/Shell sort
Modifica il sommario
Il Bucket sort è un algoritmo di ordinamento per valori numerici interi con complessità lineare O(n+m), dove n è la lunghezza dell'array e m è il valore massimo che può esserci nell'array. Non è basato su confronti e scambi e conviene utilizzarlo quando il valore di m è piccolo rispetto a n o comunque comparabile, altrimenti risulterebbero più veloci altri algoritmi.
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 vettore ausiliario( da ora in poi Y) dove la t-esima cella contiene la frequenza dell'elemento t nel vettore di input (da ora in poi X). Per fare un esempio, se X fosse cosi strutturato:
Y sarebbe:
Una volta costruito Y con le frequenze di ogni elemento di X si può ricostruire il 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.

## Analisi dell'algoritmo

La complessità del Bucket Sort è O(n + m) infatti la complessità per inizializzare il vettore Y e leggerlo per ricostruire X è O(m), mentre la complessità del terzo ciclo for è O(n). Da questo possiamo capire l'utilità del Bucket Sort: infatti se m = O(n) allora la complessità totale dell'algoritmo è O(n).

## Altri progetti

Altri progetti
* Wikipedia
* Wikipedia contiene una voce su questo algoritmo