Radix Sort Algorithm | Board Infinity

Introduction

The radix sort algorithm and its C++ implementation are covered in this article.

An integer sorting technique known as radix sort groups keys by digits that have the same meaningful position and value to order data with integer keys (place value). It sorts an integer array by leveraging Counting Sort. Radix sort works on data types more than only integers since strings may be represented by integers (by hashing the strings to integers). Radix sort may operate in linear time since it is not comparison-based, and as a result, its running time is not constrained by O (n.logn)

Working of Radix Sort

Specify [121, 432, 564, 23, 1, 45, 788] as the starting array.
Find the array's biggest element or max. Let X represent the maximum number of digits. We have to go over all of the important locations for all components, which requires us to compute X. The greatest number in this array [121, 432, 564, 23, 1, 45, 788] is 788. It is three digits. Consequently, the loop should increase to hundreds of places (3 times).
Now, visit each important location one at a time. The numerals should be sorted at each significant place using any reliable sorting method. For this, we used a counting sort.
According to the unit place digits (X=0), order the items.
Sort the items now, starting with the tens place digits.
The components should then be sorted depending on the numbers in the hundreds place.

Code

#include<iostream>
#include<list>
#include<cmath>
using namespace std;
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void radixSort(int *arr, int n, int max) {
int i, j, m, p = 1, index, temp, count = 0;
list<int> pocket[10];

for(i = 0; i< max; i++) {
m = pow(10, i+1);
p = pow(10, i);
for(j = 0; j<n; j++) {
temp = arr[j]%m;
index = temp/p;

pocket[index].push_back(arr[j]);
}
count = 0;
for(j = 0; j<10; j++) {

while(!pocket[j].empty()) {
arr[count] = *(pocket[j].begin());
pocket[j].erase(pocket[j].begin());
count++;
}
}
}
}
int main() {
int n, max;
cout << "Enter the number of elements: ";
cin >> n;
cout << "Enter the maximum digit of elements: ";
cin >> max;
int arr[n];

cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Data before Sorting: ";
display(arr, n);
radixSort(arr, n, max);
cout << "Data after Sorting: ";
display(arr, n);
}

write your code here: Coding Playground

Output:

Enter the number of elements: 10

Enter the maximum digit of elements: 3

Enter elements:

802 630 20 745 52 300 612 932 78 187

Data before Sorting: 802 630 20 745 52 300 612 932 78 187

Data after Sorting: 20 52 78 187 300 612 630 745 802 932

Complexity Analysis

Time Complexity
Best	O(n+k)
Worst	O(n+k)
Average	O(n+k)
Space Complexity	O(max)
Stability	Yes

The time complexity of the radix sort, which employs counting sort as an intermediary stable sort, is O(d(n+k)).

In this case, the counting sort's time complexity is O (n+k) where d is the number cycle. Radix sort, in comparison to other sorting algorithms, has linear time complexity, which is better than O (nlog n). It can operate in linear time if we use extremely large digit counts or a lot of additional bases, such as 32-bit and 64-bit values, but the intermediate sort occupies a lot of room. Radix sort space is inefficient as a result. Hence, software libraries do not use this sort.

Applications of Radix Sort

The Kärkkäinen-Sanders-Burkhardt DC3 method is used while creating a suffix array.
Locations with a wide range of numbers.