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

quick sorting

Radix Sorting Time complexity

Radix sorting time complexity is O(N∗logb(N)). here N is the number of elements in the list, b is the base for representing numbers.

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)));                                                                                                                                                                                                                
Output:
$ 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]


Privacy Policy  |  Copyright@2017 - All Rights Reserved.  |  Contact us   |  Report website issues in Github   |  Facebook page   |  Google+ page

Email Facebook Google LinkedIn Twitter
^