Radix Sort Algorithm in Data Structure

What is the Radix Sort Algorithm?

Radix Sort is a non-comparative sorting algorithm. It works by grouping the individual digits of the elements to be sorted. A stable sorting technique is then used to organize the elements based on their radix. It is a linear sorting algorithm.

The sorting process involves the following properties:

• Finding the maximum element and getting the number of digits of that element. This gives the number of iterations the sorting process performs.
• Grouping the individual digits of the elements at the same significant position in each iteration.
• The grouping process starts from the least significant digit and ends at the most significant digit.
• Sorting the elements based on the digits at that significant position.
• Maintaining the relative order of elements that have the same key value. This property of Radix Sort makes it a stable sort.

The final iteration returns a completely sorted list.

Working of Radix Sort Algorithm

List of integers to be sorted

Let us sort the list of integers in the above figure in ascending order using Radix Sort.

Here are the steps to perform the Radix Sort process:

Step 1) Identify the maximum element in the list. Here it is 835.

Step 2) Count its digits. 835 has 3 digits, so the number of iterations is 3.

Step 3) Determine the base. Since this is decimal, the base is 10.

Step 4) Start the first iteration.

a) First iteration

Sorting by the last digit

In the first iteration, we consider the unit place value of each element.

Step 1) Mod the integer by 10 to get the unit place of the elements. For example, 623 mod 10 gives 3, and 248 mod 10 gives 8.

Step 2) Use counting sort or another stable sort to organize the integers according to their least significant digit. From the figure, 248 falls into the 8th bucket, 623 falls into the 3rd bucket, and so on.

After the first iteration, the list now looks like this.

List after the first iteration

The list is not sorted yet and requires more iterations.

b) Second iteration

Sorting based on digits at tens place

In this iteration, we consider the digit in the tens place for the sorting process.

Step 1) Divide the integers by 10. For example, 248 divided by 10 gives 24.

Step 2) Mod the output of Step 1 by 10. 24 mod 10 gives 4.

Step 3) Follow Step 2 from the previous iteration.

After the second iteration, the list now looks like this:

List after the second iteration

The list is still not sorted completely as it is not in ascending order yet.

c) Third iteration

Sorting based on the digits at hundreds place

For the final iteration, we want to get the most significant digit. In this case, it is the hundreds place for each of the integers in the list.

Step 1) Divide the integers by 100. For example, 415 divided by 100 gives 4.

Step 2) Mod the result from Step 1 by 10. 4 mod 10 gives 4.

Step 3) Follow Step 3 from the previous iteration.

List after the third iteration

The list is now sorted in ascending order. The final iteration has been completed, and the sorting process is finished.

Pseudocode of Radix Sort Algorithm

Here is the pseudocode for the Radix Sort Algorithm:

radixSortAlgo(arr as an array)
    Find the largest element in arr
    maximum = the element in arr that is the largest
    Find the number of digits in maximum
    k = the number of digits in maximum
    Create buckets of size 0-9 k times
    for j -> 0 to k
        Acquire the jth place of each element in arr. Here j = 0 represents the least significant digit.
        Use a stable sorting algorithm like counting sort to sort the elements in arr according to the digits in the jth place
    arr = sorted elements

C++ Program to Implement Radix Sort

#include <iostream>
using namespace std;
// Function to get the largest element in an array
int getMaximum(int arr[], int n) {
    int maximum = arr[0];
    for (int i = 1; i < n; i++) {
        if (maximum < arr[i]) maximum = arr[i];
    }
    return maximum;
}
// We are using counting sort to sort the elements digit by digit
void countingSortAlgo(int arr[], int size, int position) {
    const int limit = 10;
    int result[size];
    int count[limit] = {0};
    // Calculating the count of each integer
    for (int j = 0; j < size; j++) count[(arr[j] / position) % 10]++;
    // Calculating the cumulative count
    for (int j = 1; j < limit; j++) {
        count[j] += count[j - 1];
    }
    // Sort the integers
    for (int j = size - 1; j >= 0; j--) {
        result[count[(arr[j] / position) % 10] - 1] = arr[j];
        count[(arr[j] / position) % 10]--;
    }
    for (int i = 0; i < size; i++) arr[i] = result[i];
}
// The radixSort algorithm
void radixSortAlgo(int arr[], int size) {
    // Get the largest element in the array
    int maximum = getMaximum(arr, size);
    for (int position = 1; maximum / position > 0; position *= 10)
        countingSortAlgo(arr, size, position);
}
// Printing final result
void printResult(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}
int main() {
    int arr[] = {162, 623, 835, 415, 248};
    int size = sizeof(arr) / sizeof(arr[0]);
    radixSortAlgo(arr, size);
    printResult(arr, size);
}

Output:

162 248 415 623 835

Python Program for Radix Sort Algorithm

# Radix Sort in Python
def countingSortAlgo(arr, position):
    n = len(arr)
    result = [0] * n
    count = [0] * 10
    # Calculating the count of elements in the array arr
    for j in range(0, n):
        element = arr[j] // position
        count[element % 10] += 1
    # Calculating the cumulative count
    for j in range(1, 10):
        count[j] += count[j - 1]
    # Sorting the elements
    i = n - 1
    while i >= 0:
        element = arr[i] // position
        result[count[element % 10] - 1] = arr[i]
        count[element % 10] -= 1
        i -= 1
    for j in range(0, n):
        arr[j] = result[j]

def radixSortAlgo(arr):
    # Acquiring the largest element in the array
    maximum = max(arr)
    # Using counting sort to sort digit by digit
    position = 1
    while maximum // position > 0:
        countingSortAlgo(arr, position)
        position *= 10

data = [162, 623, 835, 415, 248]
radixSortAlgo(data)
print(data)

Output:

[162, 248, 415, 623, 835]

Complexity Analysis of Radix Sort

There are two types of complexity to consider: space complexity and time complexity.

• Space complexity: O(n + b) where n is the size of the array and b is the base considered.
• Time complexity: O(d * (n + b)) where d is the number of digits of the largest element in the array.

Space Complexity of Radix Sort

Two features to focus on for space complexity:

• Number of elements in the array, n.
• The base used to represent the elements, b.

Sometimes this base can be greater than the size of the array. The overall complexity is thus O(n + b).

The following properties of the elements in the list can make Radix Sort space inefficient:

• Elements with a large number of digits.
• Base of the elements is large, like 64-bit numbers.

Time Complexity of Radix Sort

Using counting sort as a subroutine, each iteration takes O(n + b) time. If d iterations exist, the total running time becomes O(d * (n + b)). Here, “O” denotes the complexity function.

Linearity of Radix Sort

Radix Sort is linear when:

• d is constant, where d is the number of digits of the largest element.
• b is not significantly larger than n.

Comparison of Radix Sort with Other Sorting Algorithms

Radix Sort’s complexity depends on the number size. Best-case and average-case are both O(d * (n + b)). Performance varies with the inner sort — counting sort is standard, but any stable sort works.

Applications of Radix Sort Algorithm

Important applications of Radix Sort are:

• Radix Sort can be used as a location-finding algorithm where large ranges of values are involved.
• It is used to construct a suffix array in the DC3 algorithm.
• It is used in sequential, random-access machines where records are keyed by fixed-width identifiers.

FAQs