O Bucket sort trata-se de um algoritmo que não se baseia apenas na comparação entre os elementos de entrada (algoritmo de ordenação por comparação). Entretanto, é necessário supor algo a respeito dos dados de entrada. Suponha um vetor \(A\) de \(n\) elementos, em que \(0 \leq A[i] < 1, i \leq n\). Esse algoritmo tem o tempo de um caso médio igual a \(O(n)\) se os dados a serem ordenados possuírem distribuição uniforme. No caso de ordenação por comparação Insertion sort, por exemplo, o pior caso tem \(O(n^2)\). Portanto, Bucket sort oferece ganho para dados de entrada mais uniformes.
O algoritmo Bucket sort consiste nos passos seguintes.
1. Criar um novo vetor \(B\) de \(n\) "buckets" (\(B\) é um vetor de listas). Dividir o intervalo \([0,1)\) em \(n\) intervalos de mesmo tamanho e associar a cada um destes intervalos uma lista do vetor \(B\) (caso "uniform keys").
2. Transferir cada elemento do vetor \(A\) a ser ordenado para o "bucket" correspondente no vetor \(B\). O "bucket" correspondente é o elemento em \(B\) cujo intervalo associado contém o elemento de \(A\).
3. Ordenar os elementos dentro de cada "bucket" usando o algoritmo Insertion sort.
4. Concaternar os "buckets" ordernados.
Veja o seguinte exemplo, extraído do cap. 8 do livro "Introduction to Algorithms" (2009) de Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. Suponha que a entrada seja o vetor \(A\) representado abaixo.
- O vetor \(B\) é dividido em 10 "buckets" (0, 1, ..., 9), já que há \(n=10\) elementos em \(A\) para serem ordenados. Os intervalos correspondentes a cada "bucket" em B são \({[0,0.1),[0.1,0.2),...,[0.8,0.9),[0.9,1)}\).
- O elemento \(A(1)\) é transferido para \(B(7)\), pois \(0.78 \in [0.7,0.8)\). Os demais elementos são transferidos segundo a mesma lógica.
- Ao final do passo anterior, todos os elementos de \(A\) terão sido transferidos para \(B\). Usa-se, então, a ordenação Insertion sort em cada "bucket" (no capítulo 2 da referência citada há uma explicação do algoritmo Insertion sort, se você não conhecer).
- A sequência resultante ao concatenar os "buckets" \(B(0),B(1),...,B(9)\) é o vetor \(A\) ordenado.
O algoritmo em Python ficaria algo do tipo:
import math
# Função que ordena os elementos de um vetor - algoritmo "insertion sort"
def InsertionSort(A):
# realoca os elementos à esquerda até a posição desejada (ordenada)
# loop por todos os elementos, a partir do segundo, da esquerda para a direita
for j in range(1,len(A)):
key = A[j] # armazena o elemento numa variável auxiliar
i = j - 1 # contador
# percorre a lista à esquerda do elemento analisado
while i >= 0 and A[i] > key:
# Troca os elementos de lugar enquanto não chegar ao primeiro
# elemento e o elemento analisado for menor e caminha uma posição
# à esquerda
A[i+1]=A[i]
i = i - 1
A[i+1]=key
return A
# Função de ordenação Bucket sort (uniform keys)
def BucketSort_uniform(A):
# número de elementos a serem ordenados
n = len(A)
# Inicializa uma lista com os "buckets"
B = [[] for i in range(n)]
# transfere os elementos da lista original para o "bucket" correspondente em B
for i in range(n):
B[math.floor(n*A[i])].append(A[i])
# ordena os elementos em cada "bucket" usando o Insertion sort
for i in range(n):
B[i] = InsertionSort(B[i])
# concatena as listas e responde a função
return sum(B,[])
A primeira função é o algoritmo de ordenação baseado em comparação Insertion sort. A segunda função é o algoritmo de ordenação Bucket sort. O detalhe relevante na implementação desta função é que os "buckets" são indexados com \(j=0,1,...,n-1\), cada um correspondendo ao intervalo \(B(j)=\left[\frac{j}{n},\frac{j+1}{n}\right)\), o que implica que a parte inteira de \(nA(i)\) corresponde ao índice \(j\) no vetor B.
Esse algoritmo é para o caso "uniform keys", em que as chaves que identificam cada elemento a ser ordenado estão no intervalo \([0,1)\). Outro caso é o "integer keys", cuja diferença é que as chaves, inteiras, estão no intervalo \([0,N-1],N \geq 2\). Neste caso, a implementação deve considerar que o intervalo não se limita mais a \([0,1)\). O código seria assim:
# Função de ordenação Bucket sort (integer keys)
def BucketSort_integer(A):
# número de elementos a serem ordenados
n = len(A)
m = max(A) + 1
# Inicializa uma lista com os "buckets"
B = [[] for i in range(n)]
# transfere os elementos da lista original para o "bucket" correspondente em B
for i in range(n):
B[math.floor(n*A[i]/m)].append(A[i])
# ordena os elementos em cada "bucket" usando o Insertion sort
for i in range(n):
B[i] = InsertionSort(B[i])
# concatena as listas e responde a função
return sum(B,[])
Veja que o índice não é mais apenas parte inteira de \(nA(j)\), mas a parte inteira de \(\frac{nA(j)}{m}\), onde \(m\) é o máximo do vetor \(A\) acrescido de uma unidade. Como os intervalos associados são sempre abertos à direita, se dividíssemos apenas por m, o elemento máximo não teria onde ser alocado - por isso acrescentamos uma unidade.
Para testar o exemplo "uniform keys", executei as linhas abaixo.
# Executa a ordenação Bucket sort
A1 = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
A2 = [0.078, 0.017, 0.039, 0.026, 0.072, 0.094, 0.021, 0.012, 0.023, 0.068]
print(BucketSort_uniform(A1))
print(BucketSort_uniform(A2))
Usei o vetor original do exemplo (\(A1\)) e outro vetor (\(A2\)) em que todos os elementos estão no intervalo \([0,0.1)\), ou seja, são alocados em um único "bucket". Veja que a ordenação funciona para ambas as entradas: o mesmo algoritmo funciona em distribuições mais ou menos uniformes. Porém, o custo é maior para \(A2\) e o Bucket sort, neste caso, não representa qualquer ganho em relação à aplicar apenas o Insertion sort a todos os dados.
Para testar o exemplo "integer keys", executei as linhas abaixo.
A3 = [78, 17, 39, 26, 72, 94, 21, 12, 23, 68]
print(BucketSort_integer(A3))
print(BucketSort_integer(A1))
print(BucketSort_integer(A2))
Note que o a versão "integer keys" é mais geral e, portanto, pode ser aplicada também para "uniform keys". Mas, lembre-se, os algoritmos que não são apenas ordenação por comparação assumem alguma hipótese a respeito da entrada. Os vetores \(A1\) e \(A2\) são compostos por elementos menores que 1. Assim, embora a versão "integer keys" chegue ao mesmo resultado (os dados ordenados corretamente), não é tão eficiente quanto a versão "uniform keys" para \(A1\) e também não apresenta qualquer ganho em relação ao Insertion sort para ordenar \(A2\).
Observações:
1. As explicações e o exemplo do caso "uniform keys" foram retirados do capítulo 8 do livro "Introduction to Algorithms" (2009) de Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C.
2. As explicações do caso "integer keys" foram retiradas da seção 4.5.1, capítulo 4, do livro "Algorithm Design. Foundations, Analysis, and Internet Examples (2001)", de Goodrich, M. T.; Tamassia, R.