Python Program for Radix Sort

In a positional numeral system, the radix (or base) is the number of digits used to represent numbers. In this tutorial, we are going to perform a radix sorting algorithm to sort an array.

Radix Sort - A basic Introduction

Radix Sort can lexicographically sort a variety of data types, including numbers, words, and emails, although it is most commonly used to sort collections of integers and strings (that are mapped to appropriate integer keys).

• This method groups the individual digits of the same place value before sorting the items. After that, arrange the items in ascending/descending order.
• Let's say we have a 4-element array. We'll start by sorting items by the value of the unit place. Then we'll sort the items by the value of the tenth position. This procedure continues until the last major location is reached.

Let us suppose an array [354, 954, 411, 9], The below diagram will show you how radix sorting is performed:

Algorithm

As of now, we have a rough understanding of how radix sort is performed. For better understanding let's dive deep into the algorithm followed by the code:

1. Using counting_sort function to sort elements on basis of their places.
2. Calculate the count of elements.
3. Calculate the cumulative count
4. Place element in sorted order
5. define a function radix_Sort()
6. Pass parameter array and place
7. Get Maximum element
8. Apply counting_sort()
9. Now the array is sorted
10. Print the array

Program for Radix Sort

As discussed above in the algorithm, let us now dive into the programming part of the radix sort operation influenced by the algorithm.

def counting_Sort(arr, p):
    s = len(arr)
    result = [0] * s
    c = [0] * 10
    
    # count of elements
    for i in range(0, s):
        index = arr[i] // p
        c[index % 10] += 1
        
    # cumulative count
    for i in range(1, 10):
        c[i] += c[i - 1]

    # sorted order
    i = s - 1
    while i >= 0:
        index = arr[i] // p  
        result[c[index % 10] - 1] = arr[i]
        c[index % 10] -= 1
        i -= 1
        
    for i in range(0, s):
        arr[i] = result[i]


#  radix sort
def radix_Sort(arr):
    maximum = max(arr)

    p = 1
    while maximum // p > 0:
        counting_Sort(arr, p)
        p *= 10

#driver code
array = [354, 954, 411, 9]
print("The original array is: ", array)
radix_Sort(array)
print("The sorted array is: ", array)

The original array is: [354, 954, 411, 9]
The sorted array is: [9, 354, 411, 954]

Conclusion

In this tutorial, we have performed a topological sort operation in python to sort a graph. The topological sort algorithm doesn't have stability. The time complexity of the topological sort algorithm is O(n+k) and the space complexity is O(max). We can use radix sorting when there are large range numbers present.