What Is Wrong With My Radix Sort?

Note: I am using python 3. I am trying to sort a list of words in alphabetical order. This is my sort: def radix_sort(List, length): buckets = [[], [], [], [], [], [], [], [],

Solution 1:

Following on my comments, that should look like

def radix_sort(List, length):
    for i in range (length-1, -1, -1):    #for every letter "column"# Here buckets are created for each iteration
        buckets = [[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
        for word in List:    #for every word index = ord(word.azWord[i])-ord('a')   #get the index of the word
            buckets[index].append(word)     #add word object to correct bucket# Here List is reconstructed for each iteration
        List[:] = []
        for containedList in buckets:
            List.extend(containedList)

Solution 2:

for i in range (length-1, -1, -1):    #for every letter "column"for word in List:    #for every word index = ord(word.azWord[i])-ord('a')   #get the index of the word
        buckets[index].append(word)     #add word object to correct bucket

Let's take a look at this code. On the first iteration of the outer loop, you put all the words in the buckets. On the second iteration, you put all the words in the buckets again. That happens again and again on every further iteration; only once you're all done do you take the words out of the buckets and put them back in the original list.

In radix sort, when you sort, you need to create a fresh set of buckets on every iteration of the outer loop. Every time you finish putting the items in the buckets, you need to reorder the list using the buckets, rather than doing that only at the very end.

Solution 3:

Use a list comprehension when making your queue. This will make your code easier to read, as nobody wants to count all those empty bins.

buckets = [[] for i in range(26)]

Also, another way to get the bucket index, instead of assigning a variable, just put those calculations in the index.

buckets[((ord(letter)/10**i)%10) for letter in word]