Sort n numbers in range from 0 to n ^ 2 | A function to do counting sort of arr [ ] according to the digit represented by exp . ; output array ; Store count of occurrences in count [ ] ; Change count [ i ] so that count [ i ] now contains actual position of this digit in output [ ] ; Build the output array ; Copy the output array to arr [ ] , so that arr [ ] now contains sorted numbers according to current digit ; The main function to that sorts arr [ ] of size n using Radix Sort ; Do counting sort for first digit in base n . Note that instead of passing digit number , exp ( n ^ 0 = 1 ) is passed . ; Do counting sort for second digit in base n . Note that instead of passing digit number , exp ( n ^ 1 = n ) is passed . ; Driver Code ; Since array size is 7 , elements should be from 0 to 48
def countSort ( arr , n , exp ) : NEW_LINE INDENT output = [ 0 ] * n NEW_LINE count = [ 0 ] * n NEW_LINE for i in range ( n ) : NEW_LINE INDENT count [ i ] = 0 NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT count [ ( arr [ i ] // exp ) % n ] += 1 NEW_LINE DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT count [ i ] += count [ i - 1 ] NEW_LINE DEDENT for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT output [ count [ ( arr [ i ] // exp ) % n ] - 1 ] = arr [ i ] NEW_LINE count [ ( arr [ i ] // exp ) % n ] -= 1 NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT arr [ i ] = output [ i ] NEW_LINE DEDENT DEDENT def sort ( arr , n ) : NEW_LINE INDENT countSort ( arr , n , 1 ) NEW_LINE countSort ( arr , n , n ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 40 , 12 , 45 , 32 , 33 , 1 , 22 ] NEW_LINE n = len ( arr ) NEW_LINE print ( " Given ▁ array ▁ is " ) NEW_LINE print ( * arr ) NEW_LINE sort ( arr , n ) NEW_LINE print ( " Sorted ▁ array ▁ is " ) NEW_LINE print ( * arr ) NEW_LINE DEDENT