Implement Radix Sort Using Python

If you’re in a computer science background, widening your technical horizons is the best thing you should do. However, your programming skills matter the most. And one must continuously keep sharpening these skills, to become a better programmer in the future. Though there are multiple things to focus on, one specific area you must focus on is the world of data structures. Data structures in general are particular approaches to solve problems so that computer resources get used minimum. In general, there are multiple data structures you can learn and implement as well. However, we’ve covered some basic data structures before, so, now we’ll move towards some advanced data structures. Hence, today we’re going to learn how to Implement Radix Sort using Python.

 

What is Radix Sort?

 

• Unlike simpler data structures, Radix Sort uses a different sorting approach to arrange elements in sequential order.

 

• Here, elements (be it Integers or Strings) are sorted based on the position of digits i.e, from least significant to most significant.

 

• No of iterations in this sorting method may vary significantly. As iterations are directly proportional to the no of digits present in the largest element in a list/array.

 

Also Read: Implement Bubble Sort using Python

 

What’s The Approach?

 

• To make this program look cleaner and easier, we’ll divide it into three major sections.

 

• In the first part, we’ll find the largest number in an array using getMax().

 

• As for the second part, we’ll pass the exponential exp value to the counting sort function.

 

• At the final stage, we’ll apply counting sort to sort the array in ascending order w.r.t the exponential value being passed.

 

• In Counting Sort, we are going to sort array elements based on single digits only. Starting from one’s place and incrementing the exponential by 10 for each iteration. This condition is going to be executed till m/exp > 0   remains true (m holds the value of the largest integer in an array).

 

Python Program To Implement Radix Sort

 

Input:

170, 45, 75, 90, 802, 24, 2, 66

 

Output:

2 24 45 66 75 90 170 802

# Python implementation of Radix Sort

# A function to do counting sort of arr[] according to
# the digit represented by exp.
def countingSort(arr, exp1):

    n = len(arr)

    # The output array elements that will have sorted arr
    output = [0] * (n)

    # initialize count array as 0
    count = [0] * (10)

    # Store count of occurrences in count[]
    for i in range(0, n):
        index = arr[i] // exp1
        count[index % 10] += 1

    # Change count[i] so that count[i] now contains actual
    # position of this digit in output array
    for i in range(1, 10):
        count[i] += count[i - 1]

    # Build the output array
    i = n - 1
    while i >= 0:
        index = arr[i] // exp1
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1

    # Copying the output array to arr[],
    # so that arr now contains sorted numbers
    i = 0
    for i in range(0, len(arr)):
        arr[i] = output[i]

# Method to do Radix Sort
def radixSort(arr):

    # Find the maximum number to know number of digits
    max1 = max(arr)

    # Do counting sort for every digit.exp is passed. exp is 10^i
    # where i is current digit number
    exp = 1
    while max1 / exp > 0:
        countingSort(arr, exp)
        exp *= 10


# Driver code
arr = [170, 45, 75, 90, 802, 24, 2, 66]

# Function Call
radixSort(arr)

for i in range(len(arr)):
    print(arr[i])