A Radix Sort Tutorial Using Python

Sorting algorithms are one of the most important concepts under data structure, one of the sorting algorithms that provide fast execution and in some ways, performs better than the comparison-based sorting algorithms is Radix sort. This algorithm is a non-comparison-based sorting algorithm and is popular because of its fast execution.

 

The Radix sort algorithm is based on the counting sort and provides a method to sort the given number of unsorted elements, these elements could be a number or a string. 

 

In this blog, we will compare this non-comparison-based sorting algorithm with comparison-based sorting algorithms like quicksort and merge sort.

 

 

Radix Sort Tutorial 

 

Radix sort is also popularly known as bucket sort algorithm, it doesn’t use comparison to sort the list, in simple words, it is not a comparison-based sorting algorithm like merge sort, bubble sort, quicksort, insertion sort, and selection sort. 

 

We also know that the best time complexity for sorting through a comparison-based sorting algorithm is o(nlogn), therefore, we will also calculate the time complexity of radix sort in order to compare it with other sorting algorithms.

 

Our first step in the radix sort algorithm is to find the maximum number in an array list, the second step examines the number of digits in the maximum number, we start the sorting with the help of the least significant digit which is nothing but 1’s place of the digit, the elements with the maximum least significant digit will shift to the right place of an array.

 

For example, if an array looks like 80, 76, 43, 22, 97 then the least significant digit in 80 is ‘0’, in 76 is ‘6’, in 43 is ‘3’, in 22 is ‘2’, in 97 is ‘7’, basically, the 1’s place of the digits are examined.

 

(Also read: Selection sort using python)

 

Now the maximum least significant digit is ‘7’, therefore that element will move towards the rightmost part of an array, or in simple words, this element will be placed at last. The list after 1’s place sorting will look like-:

 

80, 22 ,43, 76, 97

 

Now, we will calculate the maximum value in ten’s place, after evaluating and performing the shift operation, we have-:

 

22, 43, 76, 80, 97

 

The list is sorted in this step, one might question that we could have found the maximum value in ten’s place first and that would be the only step, which might look appropriate in this example, but let’s change and example-:

 

32, 46, 19, 5, 83, 640, 51

 

Now first, we will examine the maximum digit in the one’s place of each number-:

 

32, 46, 19, 5, 83, 640, 51

 

The result after finding the maximum digit in the one’s place and shifting according to it would be:

 

640, 51, 32 ,83, 5, 46, 19

 

Similarly, we have to find the maximum digit in the ten’s place and makeshift accordingly-:

 

640, 51, 32 ,83, 05, 46, 19

 

The result would be-:

 

05, 19, 32, 640, 46, 51, 83

 

In this example, we could not solve the sorting problem at ten’s place, therefore, we have to move to the hundred’s position, as in the hundred’s position, there is only one number, this number will automatically move to the rightmost part of the array and all the other elements will remain unchanged and hence, the list will be sorted.

 

05, 19, 32, 46, 51, 83, 640

 

(Suggested blog: Underfitting and overfitting in ML)

 

 

Why is Radix Sort Called Bucket Sort?

 

But why is the radix sort known to be a bucket sort algorithm, what’s the perspective behind it? Well, let us take an example of an unsorted list and try to sort it again using the same method, 2but different perspectives.

 

60, 34, 12, 98, 104, 28, 51, 77, 139

 

The above list is unsorted, let us make 10 buckets from 0 to 9, these buckets will be used in every pass, let us imagine that each number with 0 in their one’s place will land up in 0th bucket, number with 1 in their one’s place will land up in 1st bucket and so on. So let’s create a bucket using the above-unsorted list-:

 

0: 60

1: 51

2: 12

3 : 

4: 34, 104

5 : 

6 : 

7: 77

8: 98, 28

9: 139

 

The above ten buckets are created on the basis of the digit at the one’s place, all those empty buckets resemble that there is no number whose digit end’s with their number. Now, all we have to do is to empty the bucket from above and from left to right.

 

60, 51, 12, 34, 104, 77, 98, 28, 139

 

Similarly, we have to evaluate the bucket for ten’s place and hundred’s place as well because the highest number in our list has a hundred’s value. We will keep iterating this process in each pass and will eventually get a sorted list. The execution is the same, but the perspective leads to the popular name of ‘bucket sort’.

 

(Recommended: Insertion sort using python)

 

Radix sort Time Complexity

 

We mentioned above that the complexity of the best case in the comparison-based sorting algorithm is o(nlogn), and in the worst case, it could be o(n2). The radix sort is a clear winner as far as complexity is concerned, the running time complexity of radix sort or bucket sort is o(n*(e+b)), where ‘n’ is the maximum number of digits in a number. 

 

For example in the number 131, there are 3 digits, therefore 3 passes are required. ‘E’ is the number of elements present in the list and ‘b’ is the number of buckets, a number of buckets in the case of numbers will be 10 and in the case of alphabets will be 26.

 

Radix Sort Python Implementation

---

from functools import reduce

def __modified(A):

    return reduce(lambda x, y: x+y, A)

     

        

def __get_num_digits(A):

    m = 0

    for item in A:

        m = max(item, m)

    return len(str(m))

 

def radix(A, num):

    for digits in range(0, num):

        B = [[] for i in range(10)]

        for item in A:

            n= item//10**(digit)%10

            B[num].append(item)

        A = __modified(B)

        

    return A

 

def main():

    A = [55,45,2,289,213,1,288,53,2]

    num = __get_num_digits(A)

    A = radix(A, num)

    print(A)

---

Comparison of Radix Sort with Other Sorting Algorithm

 

Radix Sort VS QuickSort

 

One might think that with the better complexity of radix sort, it should be used more often but that’s really not the case, if we compare it with quicksort, it works faster for a set of larger input but the space complexity is not as good as its time complexity, therefore it is not a space-efficient algorithm, the algorithm takes extra space because it is based on the counting sort algorithm.

 

Radix Sort VS Merge Sort

 

We have already discussed that in terms of time complexity radix sort might be better than the Quicksort algorithm, therefore, as quicksort is superior to merge sort, radix sort automatically tends to perform better than merge sort.

 

However, one disadvantage of using radix sort is that because it uses buckets, not all data types can be applied to this algorithm, or where the inputs are closely packed, this algorithm performs poorly. The conclusion is that merge sort is a safer choice than radix sort.

 

Conclusion

 

In this blog, we have discussed the working of radix sort and why it is popularly known as a bucket sort algorithm, we have also discussed the time complexity of the radix sort. 

 

In the middle section of the blog, we learned about the python implementation of radix sort and at last, we compared radix sort with comparison-based sorting algorithms like quicksort and merge sort.