Updated April 17, 2023
Introduction to Radix Sort in Python
The sorting technique in which the elements of the given array to be sorted are grouped into individual digits based on the place value, which is then sorted in either ascending order or descending order, is called Radix sort in Python, whose time complexity is O(nk) where n is the size of the input array to be sorted and k is the length of the digit in the array to be sorted and radix sort in Python includes an intermediate sort called counting sort, and radix sort are used to implement DC3 algorithm and in places where large numbers are involved.
The function to perform Radix sort is as follows:
def radixSort(array):
maximum_value = max(array)
place_value = 1
while maximum_value // place_value > 0:
countingSort(array, place_value)
place_value *= 10where the array is the input array to be sorted using the radix sort technique,
maximum_value is the maximum_value present in the given array and
place_value represents the place value of individual digits in a number and
countingSort is the countingSort function to perform the intermediate sort.
Working of Radix sort algorithm in Python
- The first step in the Radix sort algorithm is to is find the largest element in the array using the max() function in python and determining the number of digits in the largest number.
- Then the most significant digits place value of the largest number is considered, and the most significant digit of each element in the array is sorted using the countingSort algorithm.
- Then the next significant digits place value of each element in the array is sorted again using the countingSort algorithm, and this process is repeated until all the digits in their place values are sorted.
Examples of Radix sort in python
Different examples are mentioned below:
Example #1
Python program to sort the elements of the given array by implementing Radix sort algorithm and then display the sorted elements of the array as the output on the screen:
Code:
#defining countingsort function to sort the given elements based on their significant digits place value
def countingSort(input_array, place_value):
arraysize = len(input_array)
output = [0] * arraysize
count = [0] * 10
#determining the count of the elements in the array
for a in range(0, arraysize):
arrayindex = input_array[a] // place_value
count[arrayindex % 10] += 1
#determining the cumulative count of the elements in the array
for b in range(1, 10):
count[b] += count[b - 1]
#placing the elements of the array in sorted order
a = arraysize - 1
while a >= 0:
arrayindex = input_array[a] // place_value
output[count[arrayindex % 10] - 1] = input_array[a]
count[arrayindex % 10] -= 1
a -= 1
for a in range(0, arraysize):
input_array[a] = output[a]
#defining radix sort function to sort the elements of the array using countingsort function
def radixSort(input_array):
maximum_value = max(input_array)
place_value = 1
while maximum_value // place_value > 0:
countingSort(input_array, place_value)
place_value *= 10
input_data = [600, 400, 500, 200, 100, 800]
print("The elements of the array to be sorted are:\n")
print(input_data)
print("\n")
radixSort(input_data)
print("\n")
print("The elements of the array after sorting are:\n")
print(input_data)The output of the above program is shown in the snapshot below:
In the above program, we are defining the countingsort function to sort the given elements based on their significant digits place value. Then we are determining the count of the elements in the array. Then we are determining the cumulative count of the elements in the array. Then we are placing the elements of the array in sorted order. Then we define the radix sort function to sort the array elements using the countingsort function and then display the elements of the sorted array as the output on the screen.
Example #2
Python program to sort the elements of the given array by implementing Radix sort algorithm and then display the sorted elements of the array as the output on the screen:
Code:
#defining countingsort function to sort the given elements based on their significant digits place value
def countingSort(input_array, place_value):
arraysize = len(input_array)
output = [0] * arraysize
count = [0] * 10
#determining the count of the elements in the array
for a in range(0, arraysize):
arrayindex = input_array[a] // place_value
count[arrayindex % 10] += 1
#determining the cumulative count of the elements in the array
for b in range(1, 10):
count[b] += count[b - 1]
#placing the elements of the array in sorted order
a = arraysize - 1
while a >= 0:
arrayindex = input_array[a] // place_value
output[count[arrayindex % 10] - 1] = input_array[a]
count[arrayindex % 10] -= 1
a -= 1
for a in range(0, arraysize):
input_array[a] = output[a]
#defining radix sort function to sort the elements of the array using countingsort function
def radixSort(input_array):
maximum_value = max(input_array)
place_value = 1
while maximum_value // place_value > 0:
countingSort(input_array, place_value)
place_value *= 10
input_data = [20, 10, 50, 70, 30]
print("The elements of the array to be sorted are:\n")
print(input_data)
print("\n")
radixSort(input_data)
print("\n")
print("The elements of the array after sorting are:\n")
print(input_data)The output of the above program is shown in the snapshot below:
In the above program, we are defining the countingsort function to sort the given elements based on their significant digits place value. Then we are determining the count of the elements in the array. Then we are determining the cumulative count of the elements in the array. Then we are placing the elements of the array in sorted order. Then we define the radix sort function to sort the array elements using the countingsort function and then display the elements of the sorted array as the output on the screen.
Recommended Articles
This is a guide to Radix sort in python. Here we discuss the concept of Radix sort in Python with corresponding programming examples and their outputs to demonstrate them. You may also have a look at the following articles to learn more –
