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()