Radix Sort Algorithm Explained with Examples

We are discussing Sorting Algorithms now. If you want, you can refer them too.

1. Sorting Algorithms
2. Counting Sort Algorithm — A brief explanation with an example
3. Counting Sort Algorithm: Implementation in Java, an analysis of stability, parallelizability, and the Time and Space Complexities

In this article, we are going to explore a linear sorting technique called Radix Sort.

In our last article, I asked a question.

Point to think : What will happen if the array to be sorted is this? Will you still prefer to use Counting Sort? Why?{10, 50, 100000, 500, 30, 900, 5}

In this array, the elements are in the range of [5,100000]. That is, [1,n²]. This can result in the algorithm going O(n²) which is worse than the worse case of Counting Sorting. We are preferring linear sorting to perform faster than O(nlogn). But here, Counting Sort can go to O(n²). So what shall be done?

In these types of situation we can use Radix Sort!

Radix sort is an integer sorting algorithm that sorts data with integer keys by clustering the keys together based on the individual digits that have the same significant position and value (place value). To sort an array of numbers, Radix sort employs counting sort as a subroutine. Radix sort works on data types other than integers because integers can be used to represent strings (by hashing the strings to integers).

The least relevant digit is sorted first, followed by the most significant digit.
The number of runs required by the Radix sort algorithm is equal to the number of digits present in the largest number in the set of numbers. For example, if the largest number is a four-digit number, the list is sorted four times.

Radix Sort Algorithm

radixSort(array)
  d <- maximum number of digits in the largest element.
  create d buckets of size 0-9.
  for i <- 0 to d
    sort the elements according to i th place digits using 
    countingSort.
countingSort(array, d)
  max <- find largest element among dth place elements.
  initialize count array with all zeros.
  for j <- 0 to size
    find the total count of each unique digit in dth place of
    elements and store the count at jth index in count array.
  for i <- 1 to max
    find the cumulative sum and store it in count array itself.
  for j <- size down to 1
    restore the elements to array.
    decrease count of each element restored by 1.

Let’s see how it works by using a simple example.

A: [150, 56, 85, 60, 1202, 924, 12, 45]

Sorting by the least significant digit (1s place) yields.

B: [150, 60, 1202, 12, 924, 85, 45, 56]

Here, we keep 1202 before 12 because it appeared before 12 in the original (A) list, and we do the same for pairs 150 and 60 and 85 and 45.

Sorting by the next digit (10s place) yields.

C: [1202, 12, 924, 45, 150, 56, 60, 85]

Here, we keep 150 before 56 because it appeared before 56 in the 2nd/ previous (B) list.

Sorting by the next digit (100s place) yields.

D: [12, 45, 56, 60, 85, 150, 1202, 924]

Sorting by the next digit (1000s place) yields.

E: [12, 45, 56, 60, 85, 150, 924, 1202]

It is done. We have sorted the given array. As we had 4 digits at maximum, we sorted the digits starting from 1s 10s 100s and 1000s.

Check the following sorting as well.

Conclusion

Let’s analyse the algorithm and see how it can be implemented in the next article.

If you want, you can refer the previous articles related with the Sorting Algorithm listed below.

1. Sorting Algorithms
2. Counting Sort Algorithm — A brief explanation with an example
3. Counting Sort Algorithm: Implementation in Java, an analysis of stability, parallelizability, and the Time and Space Complexities

Hope the article can help. Share your thoughts too.

More content at plainenglish.io