Radix Sort

An Efficient Sorting Algorithm that Sorts Numbers Digit by Digit

Introduction

Radix Sort is a non-comparative sorting algorithm that sorts elements by processing them digit by digit.This method sorts numbers by looking at one digit at a time. Instead of comparing the whole numbers, it sorts them based on their digits, starting from the zero place (least significant digit) then moving to the ten place (next digit to the left), and so on.

Why is it called Radix Sort?

Radix refers to the base of a number system. For example, in decimal numbers, the radix (or base) is 10 because it uses digits from 0 to 9. Radix Sort takes advantage of this by sorting based on these digits.

How Radix Sort Works?

1

Find the largest number in the array.

  • Finding the largest number ensures that we know how many digits (or places) we need to sort. This step determines the number of iterations (or passes) required to process all digits of every number.
2

Start with the zero place.

  • Sort the numbers based on this digit using a stable sorting method like Count Sort.
  • Move to the next place (ten place) and sort again.
  • Repeat this process for each place (hundred place, thousand place, etc.) until all digits are sorted.
3

The array will be fully sorted after the last place is processed.

Implementation of Radix Sort

//radixsort.cpp
#include <iostream>
#include <vector>
using namespace std;
void countSort(vector<int> &v, int pos)
{
int n = v.size();
vector<int> freq(10, 0);
for (int i = 0; i < n; i++)
{
    freq[(v[i] / pos) % 10]++;
}
for (int i = 1; i < 10; i++)
{
    freq[i] += freq[i - 1];
}
vector<int> ans(n);
for (int i = n - 1; i >= 0; i--)
{
    ans[--freq[(v[i] / pos) % 10]] = v[i];
}
for (int i = 0; i < n; i++)
{
    v[i] = ans[i];
}
}
void radixSort(vector<int> &v)
{
int max_ele;
for (auto x : v)
{
    max_ele = max(max_ele, x);
}
for (int pos = 1; max_ele / pos > 0; pos *= 10)
{
    countSort(v, pos);
}
}
int main()
{
vector<int> v{0,500,3,77,12,56,777};
radixSort(v);
for (int ele : v)
{
    cout << ele << " ";
}
}

Time Complexity

Finding the Maximum Element: O(n)

  • To determine the number of digits d in the largest number.

Counting Sort for Each Digit: O(n + k)

  • Counting Sort runs once for each digit, where k is the range of digits, typically k = 10 for decimal numbers.

Number of Digits (d) in the Largest Number:

  • The process is repeated d times.

Time Complexity:O(d⋅(n+k))≈ O(n⋅d) since k = 10 is constant.

Space Complexity

For Auxiliary Array Space in Count Sort:O(n+k)

Space Complexity:O(n+k)