There are a couple of things that seem wrong in your code. I'm not sure exactly which of these is causing the issues you're seeing, but probably all of them need to be fixed before you will get the right results.
First, a quick note: You can simplify the logic a bit by only using a single integer to find the right digit in each of your numbers. I suggest a value that starts at zero and goes up to some value (the number of digits you want to sort on). You can find that digit's value for a given list item with sig_dig = num // 10**k % 10
. The //
operator forces Python to use "floor division", truncating off the non-integer part of normal division.
Anyway, the first issue is that you're looping on val == 0
, but you never modify val
, and you return a value before the end of the loop (so you'll never do it more than once anyway). You can fix this by calculating the number of digits in the longest value of your list with something like max_digits = int(math.ceil(math.log(max(lst), 10)))
. Then you can make your loop much simpler: for k in range(max_digits):
The next issue I see is that you're probably not getting the values from the bins back into a list properly. You're only calling dequeue
once, but you should probably be calling it repeatedly until the queue is empty. Or, if I'm misunderstanding the Queue
API you're using and dequeue
returns all the queue's values, you need to use extend
to add them all to the list at once.
Here's what I think you want to have, in the end:
import math
from my_queue import Queue
def rsort(n):
'''(list of int) -> list of int
'''
bin_list = [Queue for _ in range(10)]
max_digits = int(math.ceil(math.log(max(lst), 10))) # calculate # of digits
for k in range(max_digits):
for num in alist:
sig_dig = num / 10**k % 10 # find digit's value
bin_list[sig_dig].enqueue(num)
n = [] # we can reuse the name `n`, rather than using a different name
for bins in bin_list:
while not bins.is_empty(): # loop to dequeue all values
n.append(bins.dequeue())
return n # the return statement is outside the loop!