In computer science, radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered. For this reason, radix sort has also been called bucket sort and digital sort.
Radix sort works by grouping the keys by individual digits that share the same significant position and value (place value). Radix sort uses counting sort as a subroutine to sort an array of numbers. Because integers can be used to represent strings (by hashing the strings to integers), radix sort works on data types other than just integers. Because radix sort is not comparison based.
/**
* @file radix_sort.cpp
* @author Huzaifa Arain ([email protected])
* @brief Implementation of Radix Sort Algorithm
* NOTE : UNDERSTANDING OF COUNTING SORT ALGORITHM IS REQUIRED
* @version 0.1
* @date 2019-10-02
*
* @copyright Copyright (c) 2019
*
*/
#include <bits/stdc++.h>
using namespace std;
/**
* @brief Helper function to print array
*
* @param A int type array
* @param n int type size of array
*/
void print_array(int A[],int n);
/**
* @brief Get the maximum int value
*
* @param A int type array
* @param n int type size of array
*
* return int type value
*/
int get_MaxInt(int A[],int n);
/**
* @brief Count Sort algorithm
*
* @param A int type array
* @param n int type size of array
* @param p int type place value 1,10,100 .... depend on number base system
*/
void countSort(int A[],int n,int p,int BaseSystem);
int main(int argc, char const *argv[])
{
int n = 5;
int BaseSystem = 10;
int InputArray[n] = {677,25,366,85,100};
int MaxValue = get_MaxInt(InputArray,n);
cout<<"Input Array is ";
print_array(InputArray,n);
cout<<"Maximum value in input array is "<<MaxValue<<endl;
for(int place = 1;MaxValue/place > 0;place *= BaseSystem){
cout<<"Start sorting based on "<<place<<" place"<<endl;
countSort(InputArray,n,place,BaseSystem);
}
return 0;
}
void countSort(int A[],int n,int p,int BaseSystem){
int Aux[BaseSystem] = {};
for (int i=0;i<n;i++){
int AuxIndex = (A[i] / p) % BaseSystem;
Aux[AuxIndex]++;
}
cout<<"Auxiliary Array after counting occurrences ";
print_array(Aux,BaseSystem);
int AccumSum = 0;
for(int i = 0;i<=BaseSystem;i++){
AccumSum += Aux[i];
Aux[i] = AccumSum;
}
cout<<"Auxiliary Array after accumulative sum ";
print_array(Aux,BaseSystem);
int tmpArr[n] = {};
for (int i = n-1;i >= 0;i--){
int AuxIndex = (A[i] / p) % BaseSystem;
tmpArr[ Aux[ AuxIndex ] - 1] = A[i];
Aux[ AuxIndex ] = Aux[ AuxIndex ] - 1;
}
// Copy the sorted elements from temporary array to
// original array
for (int i = 0;i<n;i++){
A[i] = tmpArr[i];
}
print_array(A,n);
}
void print_array(int A[],int n){
for(int i=0;i < n;i++){
cout<<A[i]<<" ";
if(i+1 == n){
cout<<endl;
}
}
}
int get_MaxInt(int A[],int n){
int tmp = 0;
for(int i=0;i < n;i++){
tmp = max(A[i],tmp);
}
return tmp;
}We are doing abstract level analysis that's why we are not interested in constants and are only interested in iterations.
for(int place = 1;MaxValue/place > 0;place *= BaseSystem){
cout<<"Start sorting based on "<<place<<" place"<<endl;
countSort(InputArray,n,place,BaseSystem);
}Above loop will run d times. d is highest number of digits in the maximum number of array If the array = {100,20,3,11,222,3333} then the maximum no is 3333 and it has 4 place values which are ones, tens, hundreds and thousands.
countSort(InputArray,n,place,BaseSystem);We already know the time complexity of count sort which is O(n+k) so our equation will look something like T(n) = d * (n+k).
So the time complexity we get is Time Complexity: O(d(n+k))
and for the space we know that count sort algorithm is creating an auxiliary array of size k and an output array of size n which gives us Space Complexity: O(d(n+k))