Radix Sort Algorithm with C++ Code | Sorting Algorithms | Data Structures & Algorithms

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. Typically Radix sort uses counting sort as a subroutine to sort. Radix sort has linear time complexity which is better than O(nlog n) of comparative sorting algorithms.

• Time complexity: O(d(n+k))
• Space complexity: O(n+k)

Where d is the no of max digits of the largest no in the digit, n is the no of elements in the list and k is the range of unique elements. Note – This time & space complexity is applicable for those Radix sort algorithms that use Counting Sort as sub routine internally.

Working –

• Step 1 – Take input array and find MAX number in the array
• Step 2 – Define 10 queues each representing a bucket for each digit from 0 to 9.
• Step 3 – Consider the least significant digit of each number in the list which is to be sorted.
• Step 4 – Insert each number into their respective queue based on the least significant digit.
• Step 5 – Group all the numbers from queue 0 to queue 9 in the order they have inserted into their respective queues.
• Step 6 – Repeat from step 3 based on the next least significant digit.
• Step 7 – Repeat from step 2 until all the numbers are grouped based on the most significant digit.

Radix Sort Pseudocode RadixSort(arr[], size) –

1. take input array & its size as – arr[size]
2. Get max element from this array
   1. m = GetMax(arr, size)
3. Call counting sort d times based on the no of digits in the max number m.
   1. for (int div = 1; m/div > 0; div *= 10)
      1. CountingSort(arr, size, div)

Counting Sort Pseudocode CountingSort(arr[], size, div) –

1. take arr[size]
2. create output array called – output[size]
3. take range (or no of unique elements. Default value 10 in our case)
4. create count array called – count[range] & initialize all values to 0
   1. for(int i=0 to i<range)
      1. count[i] = 0
5. Count each element & place it in the count[] array
   1. for(int i = 0 to i<size)
      1. count[ (arr[i]/div)%10 ]++
6. Modify count[] array to store previous counts (cumulative)
   1. for(int i = 1 to i < range)
      1. count[i] += count[i – 1];
7. Place elements from input array arr[] to output array output[] using this count[] array that has the actual positions of elements
   1. for(int i=0 to i<size)
      1. output[count[ (arr[i]/div)%10 ] – 1] = arr[i]
      2. count[ (arr[i]/div)%10 ]–
8. Transfer sorted values from output[] array to input array arr[]
   1. for(i=0 to i<size)
      1. arr[i] = output[i]

C++ Program to Implement Radix Sort –

// C++ implementation of Radix Sort 
#include<iostream> 
using namespace std; 
  
// A utility function to get maximum value in arr[] 
int getMax(int arr[], int size) 
{ 
    int max = arr[0]; 
    for (int i = 1; i < size; i++) 
        if (arr[i] > max) 
            max = arr[i]; 
    return max; 
} 
  
void CountingSort(int arr[], int size, int div) 
{ 
    int output[size]; 
    int count[10] = {0}; 
  
    for (int i = 0; i < size; i++) 
        count[ (arr[i]/div)%10 ]++; 
  
    for (int i = 1; i < 10; i++) 
        count[i] += count[i - 1]; 
  
    for (int i = size - 1; i >= 0; i--) 
    { 
        output[count[ (arr[i]/div)%10 ] - 1] = arr[i]; 
        count[ (arr[i]/div)%10 ]--; 
    } 
  
    for (int i = 0; i < size; i++) 
        arr[i] = output[i]; 
} 
  
 
void RadixSort(int arr[], int size) 
{ 
    int m = getMax(arr, size); 
    for (int div = 1; m/div > 0; div *= 10) 
        CountingSort(arr, size, div); 
} 
  

int main() 
{ 
	int size;
	cout<<"Enter the size of the array: "<<endl;
	cin>>size;
	int arr[size];
	cout<<"Enter "<<size<<" integers in any order"<<endl;
	for(int i=0;i<size;i++)
	{
		cin>>arr[i];
	}
   cout<<endl<<"Before Sorting: "<<endl;
   for(int i=0;i<size;i++)
	{
		cout<<arr[i]<<" ";
	}
	
	RadixSort(arr, size); 
   
	cout<<endl<<"After Sorting: "<<endl;
   for(int i=0;i<size;i++)
	{
		cout<<arr[i]<<" ";
	} 
    
    return 0; 
}

YouTube video tutorial –