Implementazioni di algoritmi/Bucket sort

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:

 posizione 1  2 3 4 5 6 7 8 9 
 elemento  10 2 8 3 2 4 4 1 5

Y sarebbe:

 posizione  1 2 3 4 5 6 7 8 9 10
 elemento   1 2 1 2 1 0 0 1 0 1

Una volta costruito Y con le frequenze di ogni elemento di X si può ricostruire il vettore ordinato, analizzando Y dalla prima cella:

1. Se Y[k]=0 passa alla cella successiva di Y.
2. Se Y[k]=c>0 aggiungi c volte il valore k in X.

Pseudo-codice

 IntegerSort(array X, intero M)
   sia Y un array di dimensione m   //Dichiarazione della struttura di appoggio
   for i ← 1 to m do                
     Y[i] ← 0                       //Inizializzazione del vettore Y
   for i ← 1 to n do
     Y[X[i]] ← Y[X[i]] + 1          //Costruzione del vettore delle frequenze
   j ← 1
   for i ← 1 to m do
     for z ← 1 to Y[i] do          //Ricostruzione del vettore di X sulla base di Y
       X[j] ← i
       j ← j + 1

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).

Implementazioni

C

void bucket_sort(int *A, int m)
{
	int *count = (int*)malloc(m*sizeof(int));
	int i,j,z;

	for(i=0; i<m; i++)
		count[i]=0;

	for(i=0; i<m; i++)
		count[A[i]]++;

	j=0;
	for(i=0; i<m; i++)
		for(z=0; z<count[i]; z++)
			A[j++] = i;

	free(count);
}

C++

void bucket_sort(int *A, int m)
{
	int *count = new int[m];
	int i,j,z;

	for(i=0; i<m; i++)
		count[i]=0;

	for(i=0; i<m; i++)
		count[A[i]]++;

	j=0;
	for(i=0; i<m; i++)
		for(z=0; z<count[i]; z++)
			A[j++] = i;

	delete[] count;
}

Altri progetti

Altri progetti

• Wikipedia

• Wikipedia contiene una voce su questo algoritmo