Introduction

The Radix sort sorts the elements based on the digits of unit place and then we sort the digits based on tenth place. This process continues till we reach the last significant place value.

Our task is to sort the elements of array using Radix Sort.

Program

def csort(ip_array, i, arr_len):
    output = [0] * (arr_len)
    temp = [0] * (10)
    for ele in range(0, arr_len):
        idx = (ip_array[ele]/i)
        temp[int((idx)%10)] += 1

    for ele in range(1,10):
        temp[ele] += temp[ele-1]

    ele = arr_len-1
    while ele >= 0:
        idx = (ip_array[ele]/i)
        output[ temp[ int((idx)%10) ] - 1] = ip_array[ele]
        temp[int((idx)%10)] -= 1
        ele -= 1


    ele = 0
    for ele in range(0,len(ip_array)):
        ip_array[ele] = output[ele]
def sort(ip_array):
    max_ele = max(ip_array)
    i = 1
    while max_ele/i > 0:
        csort(ip_array,i, len(ip_array))
        i *= 10
       
ip_arr = [85, 151, 12, 3, 1]
sort(ip_arr)
print("The sorted array is :")
for i in range(len(ip_arr)):
    print(ip_arr[i])

Output

Explanation

The steps followed for Radix sort are:

1. Firstly we find the max element in the given array. The max element in our array is 151. 151 has 3 digits, so the loop will go 3 times till hundred place.
2. Now we sort the elements based on unit place digits using counting sort algorithm.
3. Now we sort the element based on tenth place.
4. And then in 3^rd iteration we will sort the elements at hundredth place value.
5. Return the sorted array.