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:
- definir e criar os buckets (quantidade e quais elementos vão em cada um)
- colocar os elementos do array nos respectivos buckets
- ordenar cada bucket individualmente (com um algoritmo à sua escolha)
- 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]