Learn about Radix Sort in Python: How Radix Sort Works?

Introduction

Radix Sort is also a non-comparison-based sorting technique like counting sort, which is used to sort array-based data. Non-comparison means it doesn't use any comparison method to sort an array of data. There is a major drawback of counting sort that may arise in some specific conditions; that's why Radix Sort comes with a better option.

But before learning about the Radix Sort algorithm you must know about how the counting sort algorithm works? that I already have discussed in another post with step by step discussion; please visit that if the logic is not clear to you. One question may come to your mind why need to learn the Counting Sort algorithm before Radix Sort; because both work together in the Radix Sort algorithm(It follows digit-based sorting technique). Since it's a non-comparison-based algorithm, so we can't use any comparison-based sorting algorithm with it.

One more important thing is that this algorithm maintains the stability of the repeated element sequence while sorting. For example, there is an array like this:

arr = 4, 2, 2, 9, 1

In this case, there are two '2' digits. When the array will be sorted those two '2' digits will follow their relative order as they were in the main array. In this tutorial, you will learn how to perform Radix Sort in Python.

How does Radix Sort Work?

Step 1

Step 2

Step 3

Step 4

Algorithm for Radix Sort

CountingSort(array, pos_val)
    size = length of array
    initialize 'temp' array; temp = [0] * size
    initialize 'count' array; count = [0] * 10

    for i in range(0 to size)
        index = (array[i]/pos_val) % 10
        count[index] = count[index] + 1
    
    for i in range(1, size)
        count[i] = count[i] + count[i-1]

    for i in range(size-1 to 0, reverse order)
        index = (array[i]/pos_val) % 10
        temp[count[index] - 1] = array[i]
        count[index] = count[index] - 1

    for i in range(0 to size)
        array[i] = temp[i]

RadixSort(array)
    max_num = max(array)
    pos_val = 1
    while (max_num/pos_val) > 0
        CountingSort(array, pos_val)
        pos_val *= 10

Code

'''Write a program to perform Radix Sort in Python'''
def CountingSort(array, pos):
    size = len(array)
    # Creating an extra array to store the main array 
    # elements in the sorted order.
    temp = [0] * size

    # Initializing the 'count' array.
    # In this case, the range of the array elements
    # from 0 to 10.
    count = [0] * 10

    # Storing the count of each element(from the main array) 
    # in the 'count' array
    for i in range(0, size):
        ix = (array[i]/pos) % 10
        count[int(ix)] += 1

    # Updating the count array elements with 
    # the actual position of each element from the main array
    for i in range(1, 10):
        count[i] += count[i-1]

    # Iterate from the end(right to left) to maintain 
    # the stability of the algorithm.
    # This loop will iterate from size-1 to 0.
    for i in range(size-1, -1, -1):
        ix = (array[i]/pos) % 10
        temp[count[int(ix)]-1] = array[i]
        count[int(ix)] -= 1

    # Copying all the elements(sorted) from 'temp' array
    # to the main array
    for i in range(0, size):
        array[i] = temp[i]

# Radix Sort Function
def RadixSort(array):
    max_num = max(array)
    pos = 1

    while max_num/pos > 0:
        # Calling the 'CountingSort' Function
        CountingSort(array, pos)
        pos *= 10

if __name__ == "__main__":
    array = [7, 8, 299, 5, 2, 321, 88]
    RadixSort(array)
    print("----Sorted Array----")
    print(array)

Output

----Sorted Array----
[2, 5, 7, 8, 88, 299, 321]

Complexity Analysis

We're assuming the size or length of the array is 'n', the range is 'k', and the largest number from the main array is 'max'. Now the conclusion is,

Time Complexity

For all conditions: O(d*(n+k)) where d is the number of digits of the largest number

Space Complexity

For all conditions: O(max)