Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

O que é o algoritmo de ordenação Bucket sort?

+1 voto
65 visitas
perguntada Jul 2 em Ciência da Computação por Carlos A T Haraguchi (21 pontos)  

O algoritmo de ordenação Bucket sort oferece ganho em que situação? Como implementá-lo?

Compartilhe

1 Resposta

+2 votos
respondida Jul 2 por Carlos A T Haraguchi (21 pontos)  
editado Ago 2 por Carlos A T Haraguchi

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) mas também em alguma característica em especial destes elementos. Por isso, é 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.

A imagem será apresentada aqui.

  1. 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)}\).
  2. 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.
  3. 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).
  4. 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.

comentou Jul 6 por Monica Guo (41 pontos)  
Oi, Carlos! A sua explicação do algoritmo Bucket Sort ficou muito boa! Deu para entender toda a lógica do algoritmo e também entender porque a complexidade é menor se comparado a algoritmos de comparação (nessa parte talvez tenha um pequeno erro de digitação - Ω ao invés de O - mas nada que comprometa o entendimento!).
Além disso, a imagem do livro ajuda bastante a entender o passo a passo do algoritmo, um ponto bem positivo para a sua explicação.

Na implementação do algoritmo, algo que me chamou a atenção foi a maneira como você define o bucket de cada elemento A[i]. Foi uma saída muito interessante para o problema e que sem dúvida economizou várias linhas do seu código se comparado as outras alternativas (como fazer vários "ifs" para definir os intervalos, por exemplo).
comentou Jul 7 por Carlos A T Haraguchi (21 pontos)  
Oi, Monica! Muito obrigado pelos comentários, especialmente pela identificação da incorreção. Corrigi a minha resposta. O Insertion sort, conforme explicado no cap. 2 de Cormen et. al. (2009) tem O(n²). Quanto à definição dos buckets de cada elemento do vetor de entrada, apenas tentei replicar o algoritmo sugerido na mesma referência.
...