Radix Sort

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

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.

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.

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.