Radix Sort | A function to do counting sort of arr [ ] according to the digit represented by exp . ; The output array elements that will have sorted arr ; initialize count array as 0 ; Store count of occurrences in count [ ] ; Change count [ i ] so that count [ i ] now contains actual position of this digit in output array ; Build the output array ; Copying the output array to arr [ ] , so that arr now contains sorted numbers ; Method to do Radix Sort ; Find the maximum number to know number of digits ; Do counting sort for every digit . Note that instead of passing digit number , exp is passed . exp is 10 ^ i where i is current digit number ; Driver code ; Function Call
def countingSort ( arr , exp1 ) : NEW_LINE INDENT n = len ( arr ) NEW_LINE output = [ 0 ] * ( n ) NEW_LINE count = [ 0 ] * ( 10 ) NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT index = ( arr [ i ] / exp1 ) NEW_LINE count [ int ( index % 10 ) ] += 1 NEW_LINE DEDENT for i in range ( 1 , 10 ) : NEW_LINE INDENT count [ i ] += count [ i - 1 ] NEW_LINE DEDENT i = n - 1 NEW_LINE while i >= 0 : NEW_LINE INDENT index = ( arr [ i ] / exp1 ) NEW_LINE output [ count [ int ( index % 10 ) ] - 1 ] = arr [ i ] NEW_LINE count [ int ( index % 10 ) ] -= 1 NEW_LINE i -= 1 NEW_LINE DEDENT i = 0 NEW_LINE for i in range ( 0 , len ( arr ) ) : NEW_LINE INDENT arr [ i ] = output [ i ] NEW_LINE DEDENT DEDENT def radixSort ( arr ) : NEW_LINE INDENT max1 = max ( arr ) NEW_LINE exp = 1 NEW_LINE while max1 / exp > 0 : NEW_LINE INDENT countingSort ( arr , exp ) NEW_LINE exp *= 10 NEW_LINE DEDENT DEDENT arr = [ 170 , 45 , 75 , 90 , 802 , 24 , 2 , 66 ] NEW_LINE radixSort ( arr ) NEW_LINE for i in range ( len ( arr ) ) : NEW_LINE INDENT print ( arr [ i ] ) NEW_LINE DEDENT