Title: Using radix sort to sort single lists within a list of list
Tags: python;radix-sort
Question: I have a list containing:
lst = [[1, 'FANTASTIC FOUR'],[18, 'PADDINGTON'],[20, 'FANTASTIC FOUR']]
and I'm using radix sort to sort the string elements in the lst above.
The output I'm trying to achieve is:
lst = [[1,'FANTASTIC FOUR'],[20,'FANTASTIC FOUR'],[18,'PADDINGTON']]
since the first list and the last list both shares the same string, they should be grouped together.
I've tried writing a radix sort function to cater for this, but I'm getting the output:
lst = [[1, 'FANTASTIC FOUR'],[18, 'PADDINGTON'],[20, 'FANTASTIC FOUR']]
instead of:
lst = [[1,'FANTASTIC FOUR'],[20,'FANTASTIC FOUR'],[18,'PADDINGTON']]
Here's the code:
def radix_sort(lst, length):
for i in range (length-1, -1, -1):    #for every letter "column"
buckets = [[], [], [], [], [], [], [], [], [], [], [], [], [],
[],[], [], [], [], [], [], [], [], [], [], [], []]
j = 0
for word in lst:
index = ord(word[j])-ord('A')
buckets[index].append(word)    #add to bucket
lst[:] = []        #rebuild list
for containedList in buckets:
lst.extend(containedList)
return lst
lst = [[1, 'FANTASTIC FOUR'],[18, 'PADDINGTON'],[20, 'FANTASTIC FOUR']]
n = len(lst)
radix = [radix_sort(i, n) for i in lst]
print(radix)
Comment: @StephenRauch because it's part of my learning process to deal with different sorting algorithms not just the conventional sorted.

Comment: I don't think this is doing what you think it's doing. You need to debug. I don't think you've put enough effort in to claim you are stuck.

Comment: This doesn't run in 2.7 or 3.6.4 but I am curious about your sort rules. They seem to violate strict weak ordering. If the entries for 1 and 20 have to be grouped together, how do you decide if they come before or after 18?

Comment: Well, there's some sean06@example.com. The completely unused outer loop is clearly intending to do that, if it actually did anything. But since OP claims to get output, the code we are seeing here is not the actual code.

Comment: I'm referring to the unused loop index "i" which counts down from the end (of the wrong thing). Actually, @Electric, just ditch the sublists and try to figure out how to do a radix sort, if that's your goal. You can add support for key=itemgetter after you have some basic working code.

Comment: There isn't any radix sorting going on here.... you're not sorting according to each value in the first index of the nested list (the string). For this to be radix sort, you'd move from the least significant character, sort that with a stable sort, and continue sorting to the most significant character. Your sort is sorting according to the first character.... simply put: this isn't a sort, it's more like a very, very rudimentary direct hashing algorithm. Refer to https://en.wikipedia.org/wiki/Radix_sort.

Comment: @KennyOstrom the given code still seems to be intended to move from 0 to length... radix sort doesn't work from MSB to LSB.. it's not really radix sort

Comment: How is [sorted](https://docs.python.org/3/library/functions.html#sorted) inadequate?



{'source': 'StackExchangeDataset', 'subset': 'stackoverflow.com', 'metadata': {'AnswerCount': 0, 'CommentCount': 8, 'ContentLicense': 'CC BY-SA 3.0', 'CreationDate': '2018:00:03/17/18', 'FavoriteCount': 1.0, 'PostTypeId': 1, 'Tags': '<python><radix-sort>', 'Title': 'Using radix sort to sort single lists within a list of list', 'ViewCount': 579, 'id': 49331227, 'user_AboutMe': '', 'user_AccountId': 6906322.0, 'user_DisplayName': 'Electric', 'user_Reputation': 487.0, 'user_Views': 123.0, 'user_id': 6861864.0}}