Radix Sort

  1. Radix Sort Algorithm
  2. Radix Sort Example
  3. Radix Sort Algorithm Implementation
  4. Radix Sort Algorithm Complexity
Note

If you don’t know what is counting sort, then please go through the counting sort article first.

Radix sort is a non-comparative sorting algorithm. This algorithm avoids comparisons by inserting elements into buckets according to the radix (Radix/Base is the number of unique digits used to represent numbers. For example, decimal numbers have ten unique digits). It sorts elements based on the digits of individual elements. It performs counting sort on digits from least significant digit to the most significant digit. It has also been called bucket sort or digital sort and is very useful on parallel machines.

Radix Sort Algorithm

Let us assume that we have an unsorted array A[] containing n elements.

  • Find the largest element maxm in the array.
  • Sort each digit in maxm starting from least significant using a stable sorting algorithm.

Radix Sort Example

Suppose we have the array: (1851, 913, 1214, 312, 111, 23, 41, 9). We will sort it using the radix sort algorithm.

Index Input Array First Iteration Second Iteration Third Iteration Fourth Iteration
0 1851 1851 0009 0009 0009
1 0913 0111 0111 0023 0023
2 1214 0041 0312 0041 0041
3 0312 0312 0913 0111 0111
4 0111 0913 1214 1214 0312
5 0023 0023 0023 0312 0913
6 0041 1214 0041 1851 1214
7 0009 0009 1851 0913 1851

In the first iteration, we sort according to unit place and then moves towards tens, hundreds, and thousands place to get the final sorted array as 9, 23, 41, 111, 312, 913, 1214, 1851

Radix Sort Algorithm Implementation

#include<iostream>
using namespace std;
const int N = 10;

int maxm(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
    {
        if (arr[i] > max)
        {
            max = arr[i];
        }
    }
    return max;
}

void countingSort(int arr[], int n, int place) {
    int output[n];
    int count[N];

    for (int i = 0; i < N; ++i)
        count[i] = 0;

    for (int i = 0; i < n; i++)
        count[(arr[i] / place) % 10]++;

    for (int i = 1; i < N; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / place) % 10] - 1] = arr[i];
        count[(arr[i] / place) % 10]--;
    }

    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

void radixsort(int arr[], int n) {
    int max = maxm(arr, n);
    for (int place = 1; max / place > 0; place *= 10)
        countingSort(arr, n, place);
}

int main() {

    int n = 5;
    int arr[5] = {1851, 913, 1214, 312, 111};
    cout << "Input arr: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    radixsort(arr, n); // Sort elements in ascending order
    cout << "Output arr: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
}

Radix Sort Algorithm Complexity

Time Complexity

  • Average Case

Radix sort has a time complexity of O(n + b) where b is the range of input. If there are d digits in the maximum element maxm, then the time complexity of Radix Sort becomes O(d*(n + b)). Since d and b are usually small, the time complexity is of the order of [Big Theta]: O(n).

  • Worst Case

The worst-case time complexity is [Big O]: O(n).

  • Best Case

The best-case time complexity is [Big Omega]: O(n). It is the same as the worst-case time complexity.

Space Complexity

Space Complexity for the radix sort algorithm is O(n+b), where b is the range of input. It comes from count &output arrays in the radix sort. Sometimes b can be larger than n, making complexity non-linear.

Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - Sort Algorithm

  • Binary Sort
  • Heap Sort