Radix Sort is a non-comparative sorting algorithm that sorts data by grouping the individual digits of the numbers and sorting them in a specific order, starting from the least significant digit to the most significant digit. This sorting technique is also called bucket sort or digital sort.

## How Algorithm of Radix Sort works?

The radix sort algorithm works as follows:

1. Determine the maximum number of digits (d) among the numbers to be sorted.
2. For each digit, starting from the least significant digit to the most significant digit, do the following: a. Initialize the count array with all zeros. b. Count the number of occurrences of each digit in the current digit position by iterating through the input array. c. Modify the count array to show the cumulative number of occurrences of each digit. d. Rearrange the input array based on the count array and the current digit position.
3. After processing all digits, the array will be sorted.

The algorithm for Radix Sort can be described using the following pseudocode:

``````radixSort(arr, n):
max_element = getMax(arr, n)

# Perform counting sort for every digit
exp = 1
while max_element / exp > 0:
countingSort(arr, n, exp)
exp *= 10

getMax(arr, n):
max_element = arr[0]
for i in range(1, n):
if arr[i] > max_element:
max_element = arr[i]
return max_element

countingSort(arr, n, exp):
output = [0] * n
count = [0] * 10

# Store count of occurrences in count[]
for i in range(0, n):
index = arr[i] / exp
count[int(index % 10)] += 1

# Change count[i] so that count[i] now contains actual position of this digit in output[]
for i in range(1, 10):
count[i] += count[i - 1]

# Build the output array
i = n - 1
while i >= 0:
index = arr[i] / exp
output[count[int(index % 10)] - 1] = arr[i]
count[int(index % 10)] -= 1
i -= 1

# Copy the output array to arr[], so that arr[] now contains sorted numbers according to current digit
for i in range(0, len(arr)):
arr[i] = output[i]
``````

The `radixSort` function takes an array `arr` of length `n` as input and sorts it using radix sort. It first calls the `getMax` function to determine the maximum element in the array. It then iterates through each digit of the maximum element using the `exp` variable, calling the `countingSort` function for each digit.

The `getMax` function simply iterates through the array to find the maximum element and returns it.

The `countingSort` function performs counting sort on the array `arr` with length `n` using the current digit represented by the `exp` variable. It first initializes an output array `output` and a count array `count`. It then iterates through the array to count the number of occurrences of each digit, storing the count in the `count` array.

Next, it modifies the `count` array so that each element represents the starting index of that digit in the `output` array. It then builds the `output` array by iterating through the input array backwards, placing each element in its correct position in the `output` array based on the count of its digit.

Finally, it copies the sorted `output` array back into the original `arr` array, completing the sort for the current digit.

Overall, the algorithm performs counting sort on each digit of the input numbers, resulting in a sorted array.

## A Basic Example of Radix Sort with Steps

Here’s an example of how Radix Sort works:

For example, let’s say we have an array of integers: [170, 45, 75, 90, 802, 24, 2, 66].

1. The maximum number of digits is 3.
2. Starting from the least significant digit to the most significant digit, we do the following: a. Initialize the count array with all zeros: count[] = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]. b. Count the number of occurrences of each digit in the current digit position:
• For the first pass (the least significant digit), we count the number of occurrences of each digit in the one’s place:
• count[] = [2, 1, 1, 0, 1, 0, 0, 1, 0, 1]. c. Modify the count array to show the cumulative number of occurrences of each digit:
• count[] = [2, 3, 4, 4, 5, 5, 5, 6, 6, 7]. d. Rearrange the input array based on the count array and the current digit position:
• After the first pass, the array becomes: [170, 90, 802, 2, 24, 45, 75, 66]. e. Repeat steps b-d for the second pass (the tens place) and the third pass (the hundreds place) to get the sorted array: [2, 24, 45, 66, 75, 90, 170, 802].

Radix sort is an efficient sorting algorithm that can sort numbers with large ranges and multiple digits. The time complexity of radix sort is O(d * (n + b)), where n is the number of elements in the array, d is the number of digits in the maximum number, and b is the base of the number system used (usually 10). However, radix sort requires extra space to store the count array and the output array, which can be a disadvantage for large datasets.

### Example Code

Here’s a basic C++ program for Radix Sort:

```#include <iostream>
using namespace std;

// A utility function to get the maximum value in arr[]
int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}

// A function to do counting sort of arr[] according to the digit represented by exp.
void countSort(int arr[], int n, int exp)
{
int output[n];
int i, count[10] = {0};

// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;

// Change count[i] so that count[i] now contains actual position of this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];

// Build the output array
for (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 current digit
for (i = 0; i < n; i++)
arr[i] = output[i];
}

// The main function to that sorts arr[] of size n using Radix Sort
{
// Find the maximum number to know number of digits
int m = getMax(arr, n);

// Do counting sort for every digit
for (int exp = 1; m / exp > 0; exp *= 10)
countSort(arr, n, exp);
}

// A utility function to print an array
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}

// The main function
int main()
{
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}
```

The above program will output:

``````Sorted array:
2 24 45 66 75 90 170 802``````

This program sorts an array of integers using the Radix Sort algorithm. The `getMax()` function finds the maximum element in the array, which is used to determine the number of digits in the largest number. The `countSort()` function performs the counting sort on a specific digit (specified by the `exp` parameter) and the `radixSort()` function repeatedly calls `countSort()` for each digit, starting with the least significant digit and working up to the most significant digit. The `printArray()` function is a utility function used to print the sorted array.

## Complexity Analysis of Radix Sort

The time complexity of radix sort depends on the number of digits in the maximum element of the input array. If the maximum element has k digits, then radix sort takes O(kn) time, where n is the number of elements in the input array.

Since radix sort uses a stable sorting algorithm as a subroutine, such as counting sort or bucket sort, the time complexity of these subroutines also contributes to the overall time complexity of radix sort. For example, if counting sort is used as a subroutine and takes O(n+k) time, where k is the range of the input elements, then the overall time complexity of radix sort becomes O(k(n+k)).

Radix sort has a linear time complexity when k is a constant or smaller than log(n), making it faster than comparison-based sorting algorithms such as quicksort and merge sort in these cases. However, radix sort requires additional space proportional to the size of the input array, making it less space-efficient than some other sorting algorithms.

## Where is the Radix sort algorithm used?

Radix sort is primarily used when the keys in the dataset to be sorted are of fixed length, and there are a large number of keys that share the same length. Some examples of where Radix sort is used include:

1. Sorting telephone numbers or social security numbers, where each number has a fixed length.
2. Sorting fixed-length strings in a database or file system.
3. Sorting financial transaction data, where each record has a fixed number of digits representing the transaction amount.
4. Sorting IP addresses in network routing tables.

Overall, Radix sort is a useful algorithm for applications where there is a large dataset with keys of fixed length and where the keys can be easily broken down into digits or characters.

• Radix sort is a stable sort, meaning it preserves the relative order of elements with equal keys.
• It is efficient when the range of values is small, making it faster than comparison-based sorting algorithms in some cases.
• Radix sort is easy to implement and has a predictable O(nk) time complexity, where n is the number of elements and k is the number of digits or bits required to represent the maximum value.