How to Radix Sort using Queues?
Question: How do you properly radix sort a list using queues?

I'm using Python 3x.

This is my attempt using queues as bins since queues are a first-in-first-out
data structure.

    
    
    from my_queue import Queue
    def rsort(n):
        '''(list of int) -> list of int
        '''
        list_length = len(n)
        val = 0
        mod = 10
        k = 1
        bin_list = []
        alist = n
        for bins in range(0,10):
            bin_list.append(Queue())
    
        while val == 0:
            for num in alist:
                sig_dig = num % mod
                sig_dig = int(sig_dig / k)
                bin_list[sig_dig].enqueue(num)
    
            if bin_list[0].size() == list_length:
                alist.append(bin_list[0].dequeue())
    
            else:
                mod = mod * 10
                k = k * 10            
    
            new_list = []
            for bins in bin_list:
                if not bins.is_empty():
                    new_list.append(bins.dequeue())
                alist = new_list
    
            return alist
    

My code works perfectly fine with small numbers such as: `[3,2,6,5,8,7]`

but when values in the list become large like: `[240, 28, 5, 18, 140, 2]`

my program no longer sorts the list, numbers end up missing and unordered.

I've been playing around with my program a lot but I just can't fix it :(


Answer: 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!
    

