Ordinamento in tempo lineare: si può ! --- Parte 3 di 3: Bucket Sort

Bucket sort effettua l'ordinamento di n elementi in un tempo ATTESO lineare, a patto che l'input sia distribuito uniformemente in un dato range di valori (es.: interi tra 0 e 100, [0,100) ).

Il funzionamento è il seguente: creiamo un array di locazioni, dette bucket, tante quanti sono gli intervalli individuabili nel range di valori (per gli interi in [0, 100), useremo 10 intervalli).

Ad ogni bucket è associata una lista.

Per ogni elemento preso dall'array di input A, effettuiamo un inserimento ORDINATO nella lista di valori associata al relativo bucket, che va individuato in base ad una regola definita da caso a caso (nel nostro esempio, il floor della divisione del valore per 10).

Avremo, ad esempio:

L'array B viene quindi “compattato” in un array “unidimensionale” di valori ordinati, in tempo lineare.

Lo pseudo-codice di questo algoritmo è molto semplice:

BUCKET-SORT(A,B)

n = length(A);

for(i=1 to n) inserisci A[i] in B[floor(A[i] / n)] in maniera ORDINATA;

concatena ordinatamente tutte le liste di B;

Il tutto viene eseguito in tempo lineare se la distribuzione dei valori in input è, come detto precedentemente, UNIFORME nel range di valori ammessi (o, al limite, finchè la somma dei quadrati delle dimensioni dei bucket è lineare nel numero totale degli elementi).