from queue import * # Given a list of nonnegative integers in base-10, this function returns the list sorted. def radixSort(list): # Make 10 queues to be bins for storing numbers as we sort them. bins = [] for i in range(10): bins.append(Queue()) # We work on the 1s place, then the 10s place, then the 100s place, etc. place = 1 # We can stop when place exceeds every number in the given list. maxNum = max(list) while place < maxNum: # Put each number in the correct bin for this pass. for num in list: # Find the digit in the current place, and place num in that bin. digit = (num / place) % 10 bins[digit].enqueue(num) # Now all numbers have been binned; put them back into the list. i = 0 for bin in bins: while not bin.isEmpty(): list[i] = bin.dequeue() i += 1 # Uncomment this line to print the partially sorted list. #print list # The bins are empty again. Advance to the next place before looping. place *= 10 return list def main(): # Test the radix sort. list = [32, 127, 5, 3456, 6, 1, 99, 245] print "unsorted:" print list print "sorting..." list = radixSort(list) print "sorted:" print list # If the user ran this file explicitly, then execute main(). if __name__ == "__main__": main()