Implementing Radix Sort in Python

This tutorial will show you how to implement Radix sort on a list in Python. Radix sort is a type of ‘counting-based‘ sorting algorithm, as opposed to ‘comparison-based’ sorting algorithms.

The main idea behind Radix sort is to perform element-by-element sorting. This is done from least significant to most significant element. For eg, in the number, 123, 3 is the least significant digit and 1 is the most significant digit.

Now that we know what Radix sort is, let’s get started.

Python Code: Radix Sort

# Function for sorting element by element

def Sort(a, y): 

  length = len(a) 

  # op is a list with length same as input list with all zeroes 
  op = [0] * length

  # Counter will keep track of number of occurrences
  counter = [0] * 10 

  for i in range(length): 
    index = int((a[i] / y)) 
    counter[(index) % 10 ] += 1

  # Counter i will now contain actual index position 
  for i in range(1,10): 
    counter[i] += counter[i-1] 

  # Inserting into op list
  i = length-1
  while i>=0: 
    index = int((a[i] / y)) 
    op[ counter[(index) % 10] - 1] = a[i] 
    counter[ (index)%10 ] -= 1
    i -= 1

  # List op has the sorted elements. Now copying op elements to original list 
  i = 0
  for i in range(0,len(a)): 
    a[i] = op[i] 


def Radix(a): 

  # To find number of digits in the maximum number in the list. 
  maximum = max(a) 

  # Each digit is sorted
  x = 1
  while (maximum / x > 0): 
    Sort(a,x) 
    x *= 10


# Main Function
        
if __name__=="__main__":
    print("Enter a list of decimal numbers seperated by a space :- ")
    ip = list(map(int,input().split()))
    print("List of Unsorted Numbers :- ")
    for i in range(len(ip)):
        print(ip[i])
        
    Radix(ip) 
    
    print("\nList of Sorted Numbers :- ")
    for i in range(len(ip)):
        print(ip[i])

First of all, when the main function executes, the user will input a list of numbers. The main function then calls the ‘Radix’ function to begin the process of radix sort.

In the Radix function, first, we find the maximum element in the list. This is done to find the maximum number of digits in a single number. Then, we begin sorting starting from the least significant digit using the Sort function.

In the Sort function, first, we create 2 lists. One, to store the output, and the other to serve as a counter. In the counter list, we are storing the number of digits of each element of the original input list. Then, we begin actually sorting the elements and begin inserting them into the final list.

Once we are done, we copy the contents of the op list into the original list. Now, the original list is sorted in increasing order.

  OUTPUT

Enter a list of decimal numbers seperated by a space :- 

7 2 1 9 10 11 4
List of Unsorted Numbers :- 
7
2
1
9
10
11
4

List of Sorted Numbers :- 
1
2
4
7
9
10
11

ANALYSIS OF RADIX SORT

If we have log(n) bits for every digit, Radix Sort performs slightly better than Quick Sort. So, for some cases, we can use Radix Sort instead of Quick Sort for a performance boost. However, Quick Sort uses hardware resources more efficiently and hence, is a better option for low-powered systems.

Time Complexity of Radix Sort : (O(n+b) * log(base b)k)

b is the base that represents the number (In case of decimals, it is 10)

k is the number of digits of the largest number in the list.

CONCLUSION

To learn more about such sorting algorithms, refer to the links below:-

How to implement Quicksort algorithm in Python

How to implement Merge Sort algorithm in Python

Leave a Reply

Your email address will not be published. Required fields are marked *