Que fait cette implémentation de tri de seau?

Question

Ceci est mon code pour le tri du seau en Python.

from random import randrange 


def insertion_sort(aList): 
    for i in range(1, len(aList)): 
     for j in range(i, 0, -1): 
      if aList[j] < aList[j-1]: 
       aList[j], aList[j-1] = aList[j-1], aList[j] 
    return aList 

def bucket_sort(aList): 
    buckets = [[]] * len(aList) 
    for index, value in enumerate(aList): 
     buckets_index = value * len(aList) // (max(aList) + 1) 
     buckets[buckets_index].append(value) 

answer = [] 

for bucket in buckets: 
    answer.extend(insertion_sort(bucket)) 
    # answer += insertion_sort(bucket) 

print(buckets[0]) 
print("\n") 
# return answer 


aList = [randrange(10) for _ in range(100)] 
print(aList) 
print("\n") 
answer = bucket_sort(aList) 
#print(answer) 

Que se passe-t-il? Lorsque je lance le code, je trouve toujours que la première liste dans les compartiments est déjà triée et les autres listes dans les compartiments sont toutes des copies de celle-ci. Ai-je besoin du tri d'insertion pour chaque liste? Que devrais-je utiliser la variable "réponse" pour ?! Je me fie principalement à this visualization.

Answer 1

Une chose que je remarque d'emblée est que vous initialisez vos compartiments variables comme buckets = [[]] * len(aList). Cela fait une liste de copies identiques de la liste vide. En tant que tel, toute modification de cette liste est répliquée dans chaque élément de buckets. Modifiez cette ligne:

buckets = [[] for _ in xrange(len(aList))] 

Pour vérifier si les listes à l'intérieur de la liste sont des objets séparés, vous pouvez vérifier leurs id:

print [id(x) for x in buckets] 

Cela devrait imprimer une liste des numéros uniques.

Answer 2

Je pense que ce type de seau serait plus efficace et plus pythonésque.

def bucket(k): 
    unique = list(set(k)) 
    values = [k.count(uni) for uni in unique] 
    result = ([unique[uni] for i in range(values[uni])] for uni in range(len(unique))) 
    result = sum(result, []) 
    return result