Summary: In this tutorial, we will learn what Radix Sort Algorithm is, how it works, and how to sort an array using the Radix Sort algorithm in C, C++, and Java.

Introduction to Radix Sort Algorithm

Radix Sort is a stable form of counting sort algorithm that is used to sort arrays values having the same radix or width.

The algorithm sorts array on the basis of the significant digits i.e. it sorts elements based on from the least significant digit to the most significant digit.

The following picture illustrate the working of Radix Sort Algorithm:

Radix sort algorithm

As you can notice the algorithm iteratively sorts array on the basic of the digits.

Here are some important points about radix sort algorithm:

  • Radix sort cannot be applied to all types of data. It can only be used with strings and positive integers (Not with Decimal numbers).
  • Strings and Integers must have same width. e.g. [22, 54, 69, 85, 45], [8596, 1025, 7456, 1298, 5200] etc. Notice that every element in the respective array has same length/digits/width.
  • Sorting starts from the rightmost position.
  • Radix sort must use counting sort or any other stable sorting algorithm.

Radix Sort Algorithm

  1. Sort array elements on the basis of the digits on the 1’s position.
  2. Then, sort the same array elements on the basis of digits on the 10’s position.
  3. Again, sort the array elements on the basis of digits on the 100’s position.
  4. Repeat the process until you are done sorting on the basis of the most significant digits.
  5. Finally, the array will be sorted.

Note: The above sorting process should be stable i.e. the integers having the same digits should not change position relatively.

Here is the implementation of the radix sort algorithm in C, C++, and Java:

C

C++

Java

Output:

In the above program, we first initialize the elements of the count_array[] with 0 using the init_with_zero(int arr[]) function.

We then calculate the width (i.e. number of significant digits) of the array element using cal_width(int v) function.

Knowing the width we iterate through the significant digits and the array elements and sort them using the counting sort stable algorithm.

The get_digit(int a, int p) function returns the digit of ‘a’ at pth position.

Radix Sort Overview

  • In-place algorithm: No extra array is used.
  • Stable Algorithm: No interchange of integers having duplicates digits.
  • O(n) time complexity: The complexity depends on the width (radix) of the elements.

In this tutorial, we learned what is Radix sort algorithm, how it works and how to sort an array using the Radix Sort Algorithm in C, C++, and Java programming languages.

Leave a Reply