C++ Program to Implement Radix Sort

This is a C++ Program to Sort the Given Data using Radix sort.

Problem Description

1. In this algorithm sorting of data is done from least significant digit to most significant digit.
2. Here we need 10 different spaces labeled 0 to 9.
3. Assume we have ‘n’ number of inputs.
4. Let ‘d’ be the maximum number of digit the input data has.
5. The time complexity for radix sort is O(n*d).
6. Radix sort solves the problem of card sorting by sorting on the least significant digit first.

Problem Solution

1. Get the maximum value from the input array which has ‘d’ digits.
2. Starting from least significant digit, sort the data.
3. Take this data as input for next significant digit.
4. Run the iteration till d digit.
5. Display the result.
6. Exit.

Program/Source Code

C++ program to implement Radix Sort.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

#include <iostream>
 
using namespace std;
 
// Get maximum value from array.
int getMax(int arr[], int n)
{
	int max = arr[0];
	for (int i = 1; i < n; i++)
		if (arr[i] > max)
			max = arr[i];
	return max;
}
 
// Count sort of arr[].
void countSort(int arr[], int n, int exp)
{
	// Count[i] array will be counting the number of array values having that 'i' digit at their (exp)th place.  
	int output[n], i, count[10] = {0};
 
	// Count the number of times each digit occurred at (exp)th place in every input.
	for (i = 0; i < n; i++)
		count[(arr[i] / exp) % 10]++;
 
	// Calculating their cumulative count.
	for (i = 1; i < 10; i++)
		count[i] += count[i-1];
 
	// Inserting values according to the digit '(arr[i] / exp) % 10' fetched into count[(arr[i] / exp) % 10].
	for (i = n - 1; i >= 0; i--)
	{
		output[count[(arr[i] / exp) % 10] - 1] = arr[i];
		count[(arr[i] / exp) % 10]--;
	}
 
	// Assigning the result to the arr pointer of main().
	for (i = 0; i < n; i++)
		arr[i] = output[i];
}
 
// Sort arr[] of size n using Radix Sort.
void radixsort(int arr[], int n)
{
	int exp, m;
	m = getMax(arr, n);
 
	// Calling countSort() for digit at (exp)th place in every input.
	for (exp = 1; m/exp > 0; exp *= 10)
		countSort(arr, n, exp);
}
 
int main()
{
	int n, i;
	cout<<"\nEnter the number of data element to be sorted: ";
	cin>>n;
 
	int arr[n];
	for(i = 0; i < n; i++)
	{
		cout<<"Enter element "<<i+1<<": ";
		cin>>arr[i];
	}
 
	radixsort(arr, n);
 
	// Printing the sorted data.
	cout<<"\nSorted Data ";
	for (i = 0; i < n; i++)
		cout<<"->"<<arr[i];
	return 0;
}
Program Explanation

1. Take input of data.
2. Get the maximum of input data.
3. Run the countSort() till (m/exp) > 0.
4. Sort the data on the basis of the digit at (exp)th place.
5. Assign the sorted data back to arr[] array.
6. Check the condition in step 3.
7. If false, print the sorted output.
8. Exit.

advertisement
advertisement
Runtime Test Cases
 
Enter the number of data element to be sorted: 10
Enter element 1: 886
Enter element 2: 542
Enter element 3: 12
Enter element 4: 3
Enter element 5: 96
Enter element 6: 1125
Enter element 7: 54
Enter element 8: 129
Enter element 9: 3125
Enter element 10: 1
 
Sorted Data ->1->3->12->54->96->129->542->886->1125->3125

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.