Implementando bucket Sort em Python. Alguma maneira melhor de distribuir os valores nos buckets? | Python

Implementei primeiro a distribuição dos valores nos buckets:

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]

PS: Faltam alguns passos para terminar a ordenação! Está funcionando. Se eu tirar o break cada valor do array será copiado várias vezes. Alguma maneira melhor de fazer distribuição dos valores nos buckets sem o break?

Um problema adicional na minha implementacao: todos os valores com exceção dos que vieram do array são zero. Eu gostaria mesmo é de ter criado um array APENAS com esses valores e as outras posições VAZIAS? Qualquer outro valor em bucket, vai me atrapalhar no restante da implementação... Como fazer?

Olá Edson.

Fiz uma implementação baseada na exemplificada no wikipedia.

lista = randint(low=100, size=10)
print(lista)
print(ordenacao_balde(lista))

Separei em varias funções que vou detalhar agora:

Primeiro função principal a que vai receber a lista de números e chamar cada passo da operação.
```
def ordenacao_balde(lista: list) -> list:
  baldes = separa_baldes(lista)
  baldes = ordena_baldes(baldes)
  lista = junta_baldes(baldes)
  return lista
```
Criei essa função para organizar e deixar mais claros os passos da ordenação, primeiro separamos cada valor em seu respectivos baldes (separa_baldes), segundo ordenamos cada balde (ordena_baldes) e finalmente juntamos os valores dos bandes em uma nova lista (junta_baldes).
Segunda função, a separa_baldes onde passamos por cada valor da lista e o adicionamos ao balde quando o valor do item for maior que a posição do balde vezes dez ( i * 10 ).
```
def separa_baldes(lista: list) -> list:
  baldes = cria_baldes()
  for item in lista:
      i = len(baldes) - 1
      while True:
          if item > i*10:
              baldes[i].append(item)
              break
          i -= 1    
  return baldes
```
Criei também a função cria_baldes só para tirar essa responsabilidade de dentro da função separa_baldes, a unica coisa que ela faz é criar uma lista com 10 posições, onde cada posição tem uma lista vazia.
```
def cria_baldes() -> list:
  baldes = []
  for _ in range(10):
      baldes.append([])
  return baldes
```

Terceira função ordena_baldes, onde passamos por cada balde e os ordenamos pelo método sort.

def ordena_baldes(baldes: list) -> list:
  for balde in baldes:
      balde.sort()
  return baldes

Quarta função junta_baldes, onde passamos agora por cada valor em cada balde e os colocamos dentro de uma nova lista:

def junta_baldes(baldes: list) -> list:
  lista = []
  for balde in baldes:
      for item in balde:
          lista.append(item)
  return lista

Importei o randint para gerar lista com valores aleatorios para a nossa implementação ordenar:

from numpy.random import randint

Infelizmente não consegui fugir do break, as variações que fiz acabavam aumentando demais a complexidade da função.

Essa foi a minha implementação desse algoritmo de ordenação. Se você quiser que eu ajude a modificar o seu, vou precisar que explique um pouco de como imaginou o seu funcionamento.

Espero ter ajudado, Bons estudos.