Python Program for Radix Sort

What is radix sort ?

• Radix sort is the generalized bin sort.
• Radix sort key idea is to bin sort all the array elements, first on f(k) (the least significant digit, then concentrate bins for the lowest value first, again bin sort on f(k-1) digit and so on.
• Make sure each array element is appended to the end of the list, not the beginning.

Radix Sort Algorithm

• Sort the array elements using counter range(0 to 9) based on least digit value.
• Repeat the sorting for next digits till maximum element number digits.

Radix Sorting Steps

Radix Sorting Time complexity

Radix Sort Python Program

#!/usr/bin/python                                                               
                                                                                
def counting_sort(list_vals, n, place):                                         
    integer_range = 10;                                                         
    freq =[0 for i in range(0, integer_range)];                                 
    list_sorted = [0 for i in range(0, n)];                                     
                                                                                
    for i in range(0, n):                                                       
        freq[(list_vals[i]/place)%integer_range] += 1;                          
                                                                                
    for i in range(1, integer_range):                                           
        freq[i] += freq[i-1];                                                   
                                                                                
    i = n-1;                                                                    
    while (i>=0):                                                               
        list_sorted[freq[(list_vals[i]/place)%10]-1]=list_vals[i];              
        freq[(list_vals[i]/place)%10] -= 1;                                     
        i -= 1;                                                                 
                                                                                
    for j in range(0, n):                                                       
        list_vals[j]=list_sorted[j];                                            
                                                                                
def radix_sort(list_vals):                                                      
    n = len(list_vals);                                                         
    max_element = max(list_vals);                                               
    mul=1;                                                                      
    while (max_element):                                                        
        counting_sort(list_vals, n, mul);                                       
        mul *= 10;                                                              
        max_element /= 10;                                                      
                                                                                
    return list_vals;                                                           
                                                                                
if __name__ == "__main__":                                                      
    list_vals = [3, 1, 2, 3, 6, 8, 5, 4];                                       
    print("Collection before sorting: %s" % str(list_vals));                    
    print("Sorted list elements: %s" % str(radix_sort(list_vals)));                                                                                                                                                                                                                

$ python radix_sort.py 
Collection before sorting: [3, 1, 2, 3, 6, 8, 5, 4]
Sorted list elements: [1, 2, 3, 3, 4, 5, 6, 8]