# Sorts a sequence of positive integers using the radix sort algorithm. from collections import deque def radixSort( intList, numDigits ): """Radixsort""" # Create an array of queues to represent the bins. binArray = list() for k in range( 10 ): binArray.append( deque() ) # 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].append( key ) # Gather the keys from the bins and place them back in intList. i = 0 for bin in binArray : while len(bin) != 0: intList[i] = bin.popleft() i += 1 # Advance to the next column value. column *= 10 def radixSortR( intList, numDigits ): """Radix sort in reverse order (large to small)""" # Create an array of queues to represent the bins. binArray = list() for k in range( 10 ): binArray.append( deque() ) # 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].append( key ) # Gather the keys from the bins and place them back in intList. l = len( binArray ) c = 0 for i in range ( l ): j = l - i - 1 while len( binArray[ j ] ) != 0: intList[ c ] = binArray[ j ].popleft() c += 1 # Advance to the next column value. column *= 10