1

Estou tentando implementar o algoritmo bucket sort. O código abaixo implementou apenas "1 rodada" (considerando os números da direita para a esquerda) do algoritmo, em que o array [97,3,100] se transformou em [100,3,97]. Como o maior número do array é 100 deveríamos ter mais "2 rodadas" para o array terminar ordenado mas não consegui continuar. Alguma ideia?

 import numpy as np

    class BucketSort():
        def __init__(self,array):
            self.array = array
        def distribution_pass(self):
            bucket = np.empty((10,len(self.array)),dtype=int)
            bucket[:] = np.nan
            #rows =[]
           # cols = []
            for num in array:
                for j in range(bucket.shape[1]):
                    bucket[num % 10, j] = num
                    #rows.append(num%10)
                    #cols.append(j)
                    break
                    print()

            return bucket
        def gathering_pass(self):
            array = []
            self.bucket = BucketSort.distribution_pass(self)
            for i in range(self.bucket.shape[0]):
                for j in range(self.bucket.shape[1]):
                  if not np.isnan(self.bucket[i,j]):
                      #print(self.bucket[i,j])
                      array.append(self.bucket[i, j])

            return array


    def main(array):
        bucket = BucketSort(array)
        BucketSort.distribution_pass(bucket)
        array = BucketSort.gathering_pass(bucket)
        return array


    array = [97,3,100]
    print(main(array))
    #bucket = BucketSort(array)
    #print(bucket.distribution_pass())
    #print(bucket.gathering_pass())

Input: [97,3,100]

Output: [100,3,97]

1 Resposta 1

1

Existe algum motivo para usar o numpy? A menos que haja alguma razão específica, vou mostrar uma solução com listas mesmo.
A mesma pergunta vale para a classe BucketSort, precisa ser uma classe? De qualquer forma, vamos à resposta...


Basicamente, no bucket sort você tem as seguintes etapas:

  1. definir e criar os buckets (quantidade e quais elementos vão em cada um)
  2. colocar os elementos do array nos respectivos buckets
  3. ordenar cada bucket individualmente (com um algoritmo à sua escolha)
  4. juntar os buckets ordenados em um único array

Todos esses passos fazem parte do algoritmo, e você só tem a ordenação completa depois que todos executam. Se você vai disponibilizar um algoritmo para que ele ordene uma lista de elementos, então faz sentido que a função ou a classe responsável já faça todos esses passos para você.

Por isso não faz muito sentido, na função main, você ter que chamar os passos de distribuition e gathering manualmente. O algoritmo deveria fazer isso para você (no caso, a classe BucketSort que deveria saber como coordenar esses passos, e quem for usar a classe só chamaria um método sort, por exemplo). Mesmo se você não usasse uma classe, o que deveria ser disponibilizado na API é apenas uma função bucket_sort, que internamente pode chamar outras funções (como a distribution_pass e gathering_pass), mas isso é um detalhe de implementação que não interessa a quem for chamar a função e só quer a sua lista ordenada.

Outro detalhe é que você definiu que a classe recebe um array e o guarda como uma variável de instância. O problema é que assim cada instância de BucketSort só será capaz de ordenar um array (a menos que você mude o array antes de ordenar novamente, claro). Mas a meu ver a classe só deveria ter o algoritmo de ordenação, que fosse capaz de ordenar qualquer array. Ou seja, o array não deveria fazer parte de BucketSort. O que você poderia passar como parâmetros no construtor são informações relacionadas ao algoritmo em si, como por exemplo a quantidade de buckets utilizados e/ou o tamanho de cada bucket (ou nem isso, pois talvez nem importe para quem vai usar a classe).

Outro ponto confuso é que você chama distribution_pass, e depois chama gathering_pass, que por sua vez chama distribution_pass de novo (o que não seria necessário: ou você chama os 2 separadamente, ou um chama o outro internamente).

Enfim, uma alternativa seria:

from math import floor

class BucketSort:
    def __init__(self, bucket_size=5):
        self.bucket_size = bucket_size

    def sort(self, array):
        if not array: # se a lista é vazia, retorna ela mesma
            return array

        # passos 1 e 2, cria os buckets e distribui os elementos neles
        buckets = self._distribution(array)

        # passo 3, ordena os buckets
        for bucket in buckets:
            self._insertion_sort(bucket)

        # passo 4, junta os buckets
        return self._gathering(buckets)

    def _distribution(self, array):
        # passo 1, cria os buckets
        min_value = min(array)
        max_value = max(array)
        qtd_buckets = floor((max_value - min_value) / self.bucket_size) + 1
        buckets = [ [] for _ in range(qtd_buckets) ]

        # passo 2, distribui os elementos nos buckets
        for num in array:
            buckets[floor((num - min_value) / self.bucket_size)].append(num)
        return buckets

    def _insertion_sort(self, bucket):
        # ordena um único bucket, usando insertion sort
        for i in range(1, len(bucket)):
            up = bucket[i]
            j = i - 1
            while j >= 0 and bucket[j] > up:
                bucket[j + 1] = bucket[j]
                j -= 1
            bucket[j + 1] = up

    def _gathering(self, buckets):
        # passo 4, junta os buckets
        array = []
        for bucket in buckets:
            array.extend(bucket)
        return array


array = [97, 3, 100]
bs = BucketSort()
print(bs.sort(array)) # [3, 97, 100]
# ordena outro array
print(bs.sort([100, 3, -10, 97, -9, 8, 54])) # [-10, -9, 3, 8, 54, 97, 100]

Eu deixei o tamanho do bucket como um parâmetro opcional no construtor (e um valor default de 5, se nenhum for passado), mas como eu já disse, este é um detalhe de implementação que talvez nem devesse ser informado (só deixei aí para mostrar que poderia ser uma opção).

Repare que o único método que eu preciso chamar é sort. Este método recebe um array e retorna outro array ordenado, e como ele faz isso internamente não interessa a quem está chamando. Repare como ele coordena as chamadas dos demais métodos, mas quem usa a classe não precisa saber como isso é feito (isso é algo que só a classe precisa saber, pois ela é quem encapsula o algoritmo).

Por isso eu deixei os outros métodos com um _ no início do nome. Esta é uma convenção do Python para indicar que os métodos são privados. Não é exatamente como métodos privados de outras linguagens (o Python não impede que você os chame de fora da classe), mas serve para indicar que eles não devem ser usados diretamente, pois são detalhes internos de implementação que podem mudar. O único que é disponibilizado e que eu garanto que não vai mudar é o método sort: a classe garante que ele recebe um array e retorna outro array ordenado (essa garantia também é chamada de "contrato" do método: se eu receber X, retornarei Y - mas como isso é feito internamente, não importa; o contrato só diz o que é feito, mas não como).

Esta forma de fazer garante que os detalhes internos podem ser alterados sem afetar quem só quer ordenar o array. Por exemplo, se eu quiser mudar o algoritmo do passo 3 (eu usei Insertion Sort, mas poderia usar qualquer outro), ou então mudar a forma de distribuir os elementos entre buckets (desde que continue funcionando, não haveria problema), ou até mesmo criar outros métodos (como por exemplo, um só para criar os buckets) ou então eliminar alguns (fazer tudo em um único método), ou mudar o código para usar numpy em vez de listas, etc, enfim, se eu quiser fazer essas mudanças internas, eu poderia, pois quem vai usar a classe continuaria chamando apenas o método sort e tudo continuaria funcionando.

Da forma que você fez, isso não é possível, pois quem vai usar a classe precisa saber quais métodos usar e em qual ordem, e se usar errado, o array não ficará ordenado.

De qualquer forma, nesse caso não tem muita vantagem em usar uma classe, a não ser complicar à toa o código. Você poderia simplesmente usar funções:

from math import floor

def distribution(array, bucket_size):
    min_value = min(array)
    max_value = max(array)
    qtd_buckets = floor((max_value - min_value) / bucket_size) + 1
    buckets = [ [] for _ in range(qtd_buckets) ]
    for num in array:
        buckets[floor((num - min_value) / bucket_size)].append(num)
    return buckets

def gathering(buckets):
    array = []
    for bucket in buckets:
        array.extend(bucket)
    return array

def insertion_sort(bucket):
    for i in range(1, len(bucket)):
        up = bucket[i]
        j = i - 1
        while j >= 0 and bucket[j] > up:
            bucket[j + 1] = bucket[j]
            j -= 1
        bucket[j + 1] = up

def bucket_sort(array):
    if not array: # se a lista é vazia, retorna ela mesma
        return array
    buckets = distribution(array, 5)
    for bucket in buckets:
        insertion_sort(bucket)
    return gathering(buckets)

print(bucket_sort([97, 3, 100])) # [3, 97, 100]
print(bucket_sort([100, 3, -10, 97, -9, 8, 54])) # [-10, -9, 3, 8, 54, 97, 100]
3
  • Usei numpy pq nao conseguia gerar uma lista de duas dimensoes vazia. Com numpy era mais fácil... 10/04/2020 às 17:14
  • @LaurindaSouza Bom, como vc pode ver no código acima, não é tão difícil assim gerar uma lista de listas vazias. Usar o numpy pra isso eu acho exagero, pois listas já resolvem sem grandes problemas :-)
    – hkotsubo
    10/04/2020 às 17:17
  • Consegue me ajudar em pt.stackoverflow.com/questions/445497/… 10/04/2020 às 17:24

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .