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.

advertisement
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
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.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn