# Sorts a sequence of positive integers using the radix sort algorithm.
# The arrays and list queues made this version of radix sort very slow!
# Instead, using 'collections.dequeue' is a much better choice
# Radix sort implemented using 'dequeue' above is actually faster than
# quicksort and mergesort now!

from llistqueue import Queue
from array204 import Array

def radixSort( intList, numDigits ):
   # Create an array of queues to represent the bins.
  binArray = Array( 10 )           
  for k in range( 10 ):
    binArray[k] = Queue()          
    
   # The value of the current column.
  column = 1                   
  
   # Iterate over the number of digits in the largest value.
  for d in range( numDigits ):
    
     # Distribute the keys across the 10 bins.
    for key in intList :                
      digit = (key // column) % 10
      binArray[digit].enqueue( key )     
      
     # Gather the keys from the bins and place them back in intList.
    i = 0                          
    for bin in binArray :
      while not bin.isEmpty() :
        intList[i] = bin.dequeue()
        i += 1                     
      
     # Advance to the next column value.
    column *= 10