Was macht diese Bucket-Sortimplementierung?

Question

Dies ist mein Code für die Bucket-Sortierung in 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) 

Was passiert? Wenn ich den Code ausführe, finde ich immer, dass die erste Liste in Buckets bereits sortiert ist und die anderen Listen in Buckets alle Kopien davon sind. Benötige ich die Einfügesortierung für jede Liste? Wofür würde ich die Variable "answer" verwenden ?!

Ich verlasse mich hauptsächlich auf this visualization.

Answer 1

Eine Sache, die ich sofort bemerken ist, dass Sie Ihre Variablen Eimer als buckets = [[]] * len(aList) initialisieren. Dadurch wird eine Liste identischer Kopien der leeren Liste erstellt. Daher wird jede Änderung dieser Liste in jedem Element von buckets repliziert. Ändern Sie diese Zeile an:

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

Um zu überprüfen, ob die Listen in der Liste separates Objekt sind, könnten Sie ihre IDs überprüfen:

print [id(x) for x in buckets] 

Dies sollte eine Liste von eindeutigen Nummern drucken.

Answer 2

Ich denke, dass diese Eimer Art effizienter wäre und mehr pythonesque ist.

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