GoCoding.org

Program for Radix Sort using Python

by | Jun 25, 2021 | Python Programs

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

Program for Radix Sort using Python

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 3rd iteration we will sort the elements at hundredth place value.
  5. Return the sorted array.

0 Comments

Submit a Comment

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.