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 1

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!