Radix Sort in C++
What is Radix Sort in C++?
Radix Sort is a Sorting algorithm that can be only applied to numeric values. This sorting technique that sorts the elements into a logical order by grouping the individual digits of the same place value. This sorting of individual digits of same place value is done with the help of counting sort. In this article we will learn more about radix sort in C++. You can learn more about counting sort by clicking the button below.

What is Radix Sort in C++?
Radix Sort is a Sorting algorithm that can be only applied to numeric values. This sorting technique that sorts the elements into a logical order by grouping the individual digits of the same place value. This sorting of individual digits of same place value is done with the help of counting sort. In this article we will learn more about radix sort in C++. You can learn more about counting sort by clicking the button below.
Working of radix sort in C++
Following steps are followed to sort any numeric data in a logical order using radix sort :-
- Take unit place digit of each element.
- Sort the element according to their unit place using counting sort.
- Now look upon the ten’s place digit of each element.
- Sort the element according to their ten’s place using counting sort.
- Repeat the step for digit of each place value.


Algorithm for radix sort in C++
Radix-Sort (array A, int n, int d)
- for i ← 1 to d
- do sort A to sort array A on digit i
Program for radix sort in C++
Run
#include<iostream> using namespace std; //Function to get the largest element from an array int getMax(int array[], int n) { int max = array[0]; for (int i = 1; i < n; i++) if (array[i] > max) max = array[i]; return max; } //Using counting sort to sort the elements in the basis of significant places void countSort(int array[], int size, int place) { const int max = 10; int output[size]; int count[max]; for (int i = 0; i < max; ++i) count[i] = 0; //Calculate count of elements for (int i = 0; i < size; i++) count[(array[i] / place) % 10]++; //Calculating cumulative count for (int i = 1; i < max; i++) count[i] += count[i - 1]; //Placing the elements in sorted order for (int i = size - 1; i >= 0; i--) { output[count[(array[i] / place) % 10] - 1] = array[i]; count[(array[i] / place) % 10]--; } for (int i = 0; i < size; i++) array[i] = output[i]; } //Main function to implement radix sort void radixsort(int array[], int size) { //Getting maximum element int max = getMax(array, size); //Applying counting sort to sort elements based on place value. for (int place = 1; max / place > 0; place *= 10) countSort(array, size, place); } //Printing an array void display(int array[], int size) { int i; for (i = 0; i < size; i++) cout << array[i] << "\t"; cout << endl; } int main() { int array[] = {112, 400, 543, 441, 678, 675, 9, 777}; int n = sizeof(array) / sizeof(array[0]); cout<<"Before sorting \n"; display(array, n); radixsort(array, n); cout<<"After sorting \n"; display(array, n); }
Output: Before sorting 112 400 543 441 678 675 9 777 After sorting 9 112 400 441 543 675 678 777
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Time and Space Complexity for Radix Sort in C++
Time Complexity of Radix Sort
Radix Sort works by sorting numbers digit by digit. It uses a stable sorting method (like Counting Sort) for each digit.
Let:
- n = number of elements
- k = number of digits in the largest number (for example, 802 has 3 digits)
Best Case: O(n * k)
It goes through each digit of every number, even if the data is already sorted.
Average Case: O(n * k)
It still needs to process all digits of all numbers.
Worst Case: O(n * k)
Even when the numbers are in the worst possible order, it processes all digits the same way.
So, in all cases, the time complexity is O(n * k), where k depends on the number of digits in the largest number.
Space Complexity of Radix Sort
Radix Sort needs some extra space to work:
- An output array of size n to store results during sorting.
- A count array of fixed size (usually 10 for base 10 numbers) to count digits.
Space Complexity: O(n + b)
Where:
- n is the number of elements
- b is the base (for decimal numbers, b = 10)

Quiz Time

Question 1.Which of the following sorting algorithms in its typical implementation gives best performance when applied on a sorted array?
- Quick Sort
- Heap Sort
- Insertion Sort
- Merge

Question 2. What is the time complexity of Build Heap operation. Which is used to create a max(or min) binary heap from a given array.?
- O(n)
- O(log n)
- O(nlog n)
- None of the above
BUILD-HEAP(A)
heapsize := size(A);
for i := floor(heapsize/2) downto 1
do HEAPIFY(A, i);
end for
END
Although the worst case complexity looks like O(nLogn), upper bound of time complexity is O(n).
Ans: A

Quiz Time
Question 1.Which of the following sorting algorithms in its typical implementation gives best performance when applied on a sorted array?
- Quick Sort
- Heap Sort
- Insertion Sort
- Merge
Question 2. What is the time complexity of Build Heap operation. Which is used to create a max(or min) binary heap from a given array.?
- O(n)
- O(log n)
- O(nlog n)
- None of the above
BUILD-HEAP(A)
heapsize := size(A);
for i := floor(heapsize/2) downto 1
do HEAPIFY(A, i);
end for
END
Although the worst case complexity looks like O(nLogn), upper bound of time complexity is O(n).
Ans: A
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment