Radix Sort Algorithm

In this tutorial, we will examine into the concept of Radix Sort Algorithm. We’ll not only explore how it works but also assess its efficiency. Furthermore, we’ll delve into the actual implementation of this sorting technique.

While our primary focus will be on utilizing Radix Sort to arrange integers, it’s important to note that its applicability extends beyond numeric values. Radix Sort can also be employed to sort other data types, such as strings.

To maintain simplicity, we’ll specifically focus on the decimal system, representing numbers in base 10. Proficiency in sorting algorithms, like Radix Sort, is invaluable when preparing for technical interviews in software development or coding engineering roles. These algorithms can greatly aid in solving a wide array of coding problems.

The Radix Sort process bears resemblance to sorting student names in alphabetical order. In this analogy, we create 26 radixes to represent the 26 English alphabet letters. The first pass, we group students’ names based on the ascending order of their first name’s initial letter. In the subsequent pass, we group their names according to the ascending order of their second name letter, and this iterative process continues until we achieve a completely sorted list.

What is Radix Sort Algorithm?

The Radix Sort algorithm is a unique sorting method in computer science. It distinguishes itself by not relying on direct comparisons between elements, as seen in traditional sorting algorithms. Instead, it operates by creating categories based on the value of specific digits, known as the radix, within the elements. When handling elements with multiple significant digits, Radix Sort iteratively applies this categorization process to each digit while preserving the order established in the previous step until it considers every digit.

In essence, Radix Sort and Bucket Sort share a close resemblance. Bucket Sort typically moves from the Most Significant Digit (MSD) to the Least Significant Digit (LSD), while Radix Sort exhibits the flexibility to operate in both directions, i.e., from LSD to MSD or vice versa. If you’re interested in gaining a deeper understanding of Bucket Sort, you can explore its algorithm’s time complexity, pseudocode, and practical applications.

Radix Sort primarily serves as a method for sorting integers. It works by grouping integers based on their individual digits, taking into account both the position and value (place value) of each digit. Radix Sort uses Counting Sort as a subroutine to sort an array of numbers. Importantly, Radix Sort broadens its applicability beyond integers and enables its use with other data types, like strings. Since Radix Sort doesn’t rely on comparisons, it can achieve a linear running time, as opposed to the Ω(n log n) lower bound for comparison-based sorting algorithms.

Working of Radix Sort Algorithm

Now, let’s delve into the operational details of the Radix Sort Algorithm.

The sorting process in Radix Sort unfolds in the following steps:

1. First, we must identify the largest element in the given array (let’s call it ‘max’). This step helps us determine the number of digits in ‘max,’ denoted as ‘x.’ Calculating ‘x’ is essential because we’ll be working through the significant places of all elements.
2. Next, we systematically progress through each significant place one by one. In this phase, we apply a stable sorting algorithm to sort the digits within each significant place.

Let’s further illustrate the workings of Radix Sort with a practical example. To provide a clearer and more accessible explanation, we’ll take an unsorted array and apply the Radix Sort algorithm to organize it. This hands-on example will enhance your understanding of the process.

Within the provided array, the largest element, 736, consists of three digits. As a result, we will iterate through the process three times (corresponding to the hundreds, tens, and units places). Hence, three passes are necessary to sort the array.

Let’s commence with the initial pass, which involves organizing the elements based on their units’ place digits, designated as ‘x = 0.’ For this task, we employ the counting sort algorithm.

Pass 1

In the first pass, we reorganize the list based on the numerical values located in the units’ place digits, represented by ‘x = 0’.

After the first pass, the array elements are –

Pass 2

During this pass, the list undergoes sorting based on the next significant digits, which are the digits in the tens’ place.

After the second pass, the array elements are –

Pass 3

In this pass, the list is arranged by considering the next significant digits, specifically those found in the hundreds’ place.

After the third pass, the array elements are –

At this point, the array has been sorted in ascending order.

Pseudocode for Radix Sort Algorithm

Here’s a pseudocode representation of the Radix Sort algorithm:

function getMax(arr):
max = arr[0]
for element in arr:
if element > max:
max = element
return max

function countingSort(arr, exp):
n = length(arr)
output = new array of size n
count = new array of size 10 // 0 to 9, for each digit

for i from 0 to 9:
count[i] = 0

for i from 0 to n-1:
index = (arr[i] / exp) % 10
count[index] = count[index] + 1

for i from 1 to 9:
count[i] = count[i] + count[i-1]

for i from n-1 to 0:
index = (arr[i] / exp) % 10
output[count[index] - 1] = arr[i]
count[index] = count[index] - 1

for i from 0 to n-1:
arr[i] = output[i]

function radixSort(arr):
max = getMax(arr)
exp = 1

while (max / exp) > 0:
countingSort(arr, exp)
exp = exp * 10

Advantages of Radix Sort Algorithm

Here are some benefits of the Radix Sort algorithm:

1. Efficiency with Short Keys: Radix Sort performs exceptionally well when dealing with keys of limited length, which is the case when the range of elements in the array is relatively small.
2. Applied in Suffix Arrays: Radix Sort finds its utility in constructing suffix arrays, a crucial component in algorithms like Manber’s and the DC3 algorithm, which are used for various text processing tasks.
3. Stable Sorting: Radix Sort is a stable sorting algorithm, meaning that it preserves the relative order of elements with equal values. This characteristic is particularly important in scenarios where maintaining the original order of equivalent elements is essential.

Disadvantages of Radix Sort Algorithm

Here are some drawbacks associated with the Radix Sort algorithm:

1. Limited Data Type Flexibility: Radix Sort’s rigid nature makes it less adaptable to diverse data types. For each distinct data type, the algorithm requires custom adaptation, which can be cumbersome and time-consuming.
2. Higher Constant Overhead: Radix Sort typically incurs a higher constant overhead when compared to certain other sorting algorithms. This means that its performance might be less efficient for smaller datasets or in scenarios where low-latency operations are critical.
3. Space Requirements: Unlike in-place sorting algorithms like Quicksort, Radix Sort consumes additional memory space due to the need for temporary storage during the sorting process.
4. Potential Inefficiency: Radix Sort may exhibit slower performance compared to other sorting algorithms like Merge Sort and Quicksort in situations where certain operations, such as managing sub-insert lists, deletions, and isolating desired digits, are not optimized.
5. Data Type Dependency: As Radix Sort relies on the inherent structure of data types, it becomes less flexible when data types need to be changed, necessitating modifications to the sorting process.

Having considered the advantages and disadvantages of the Radix Sort algorithm, let’s explore some of its practical applications.

C Code Using Radix Sort Algorithm

Here’s a simple C code implementation of the Radix Sort algorithm for sorting an array of integers:

#include <stdio.h>
// Function to find the maximum element in the array
int getMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
// A function to perform counting sort based on a significant place (exp)
void countingSort(int arr[], int n, int exp) {
int output[n];
int count[10] = {0};
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
// Main Radix Sort function
void radixSort(int arr[], int n) {
int max = getMax(arr, n);
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, n, exp);
}
}
int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
radixSort(arr, n);
printf("\nSorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}

This code defines the Radix Sort algorithm, finds the maximum element, and performs the sorting using counting sort for each significant digit place (units, tens, hundreds, etc.). The example demonstrates sorting an array of integers.

Java Program Using Radix Sort Algo

Here’s a Java program that implements the Radix Sort algorithm to sort an array of integers:

import java.util.Arrays;
public class RadixSort {
public static void radixSort(int[] arr) {
// Find the maximum number to know the number of digits
int max = Arrays.stream(arr).max().getAsInt();
// Do counting sort for every digit
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, exp);
}
}
private static void countingSort(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
// Initialize count array
Arrays.fill(count, 0);
// Count occurrences of each digit in count[]
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
// Change count[i] so that count[i] now contains the actual
// position of this digit in output[]
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// Build the output array
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// Copy the output array to arr[], so that arr[] now
// contains sorted numbers according to the current digit
System.arraycopy(output, 0, arr, 0, n);
}
public static void main(String[] args) {
int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
System.out.println("Original array: " + Arrays.toString(arr));
radixSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}

This Java program defines the Radix Sort algorithm, finds the maximum element, and sorts the array using counting sort for each significant digit place (units, tens, hundreds, etc.). It then demonstrates sorting an array of integers.

FAQ Related to Radix Sort Algorithm

What is the difference between quicksort and radix sort?

Why is it called radix sort?

What is faster than radix sort?

For general-purpose sorting, algorithms like Quicksort and Merge Sort are often faster than Radix Sort. These comparison-based algorithms have better average-case performance for unsorted data. However, Radix Sort can outperform them on specific datasets, especially with fixed-length keys or integer data.

What is the difference between radix and count sort?

Radix Sort is a non-comparative sorting algorithm that uses Counting Sort as a subroutine to sort elements by individual digits. Counting Sort is a stable sorting algorithm that counts occurrences of each element and rearranges them. Radix Sort is typically used for multi-digit numbers, while Counting Sort works on a single-digit range.

Why radix sort is better than bucket sort?

Radix Sort is not inherently better than Bucket Sort; they serve different purposes. Radix Sort is mainly used for integers, while Bucket Sort can handle a wider range of data types. The choice between them depends on the specific data and sorting requirements.

Is radix sort divide and conquer?

No, Radix Sort is not a divide-and-conquer algorithm. It is a non-comparative sorting algorithm that sorts elements based on their digit values without dividing the array into smaller subproblems and combining solutions as divide-and-conquer algorithms do.

Does radix sort work for negative numbers?

Radix Sort can work with negative numbers, but it requires additional processing to handle them correctly. Typically, you can convert negative numbers to their positive counterparts by using an offset or store them separately, sort both positive and negative subsets, and then combine the results while preserving the relative order.

Is radix sort suitable for duplicates?

Radix Sort is suitable for handling duplicate values. It is a stable sorting algorithm, meaning it maintains the relative order of elements with equal values. This makes it a good choice when dealing with datasets containing duplicates.

What is a real life example of radix sort?

A real-life example of Radix Sort can be found in libraries or bookstores when sorting books on a shelf. Books are often organized based on their titles, starting with the first letter, then the second letter, and so on. This process is similar to Radix Sort, where elements are sorted by considering their digits or letters in a specific order.

Suggested Reads!

• History of Radix Sort Algo
• BFS Algorithm

Anshul Pal

Hey there, I’m Anshul Pal, a tech blogger and Computer Science graduate. I’m passionate about exploring tech-related topics and sharing the knowledge I’ve acquired. With two years of industry expertise in blogging and content writing, I’m also the co-founder of HVM Smart Solution. Thanks for reading my blog – Happy Learning!