#include <iostream>
#include <algorithm>
using namespace std;
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;
}
void countSort(int arr[], int n, int exp) {
int output[n];
int count[10] = {0};
// Store count of occurrences
for (int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
// Change count to position
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build output array
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// Copy output to original array
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
void radixSort(int arr[], int n) {
int max = getMax(arr, n);
// Do counting sort for every digit
for (int exp = 1; max / exp > 0; exp *= 10)
countSort(arr, n, exp);
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
printArray(arr, n);
radixSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}Output
Original array: 170 45 75 90 802 24 2 66 Sorted array: 2 24 45 66 75 90 170 802
This program teaches you how to implement the Radix Sort algorithm in C++. Radix Sort is a non-comparative sorting algorithm that sorts numbers by processing individual digits from least significant to most significant. It uses Counting Sort as a subroutine for each digit position. Radix Sort is efficient for integers with a limited number of digits.
1. What This Program Does
The program sorts an array of integers using the Radix Sort algorithm. For example:
- Input array: [170, 45, 75, 90, 802, 24, 2, 66]
- Output array: [2, 24, 45, 66, 75, 90, 170, 802]
Radix Sort processes digits from right to left (least significant to most significant), using Counting Sort for each digit position.
2. Header Files Used
-
#include <iostream>
- Provides cout and cin for input/output operations.
-
#include <algorithm>
- Provides max_element() and min_element() functions (used in some implementations).
3. Understanding Radix Sort
Algorithm Concept:
- Sorts by processing individual digits
- Starts with least significant digit (rightmost)
- Moves to more significant digits (leftward)
- Uses Counting Sort for each digit position
- Stable sorting algorithm
Visual Example:
Array: [170, 45, 75, 90, 802, 24, 2, 66]
Pass 1 (ones place): [170, 90, 802, 2, 24, 45, 75, 66] Pass 2 (tens place): [802, 2, 24, 45, 66, 170, 75, 90] Pass 3 (hundreds place): [2, 24, 45, 66, 75, 90, 170, 802]
4. Function: getMax()
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; }
How it works:
- Finds the maximum element in the array
- Needed to determine number of digits to process
- Example: max = 802 → 3 digits → 3 passes needed
5. Function: countSort()
void countSort(int arr[], int n, int exp) { int output[n]; int count[10] = {0};
// Store count of occurrences
for (int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
// Change count to position
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build output array
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// Copy output to original array
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
How it works:
- exp: current digit position (1, 10, 100, ...)
- (arr[i] / exp) % 10: extracts digit at current position
- Uses Counting Sort for the current digit
- Maintains stability by processing from right to left
Example (exp = 1, ones place):
- Extract ones digit: 170 → 0, 45 → 5, 75 → 5
- Count occurrences: count[0]=1, count[5]=2, ...
- Build sorted output based on ones digit
6. Function: radixSort()
void radixSort(int arr[], int n) { int max = getMax(arr, n);
for (int exp = 1; max / exp > 0; exp *= 10)
countSort(arr, n, exp);
}
How it works:
- Gets maximum element to determine number of passes
- exp starts at 1 (ones place)
- Each iteration: exp *= 10 (tens, hundreds, ...)
- Continues until max / exp > 0 (all digits processed)
Example (max = 802):
- Pass 1: exp = 1 (ones place)
- Pass 2: exp = 10 (tens place)
- Pass 3: exp = 100 (hundreds place)
- Pass 4: exp = 1000, max/exp = 0 → stop
7. Time and Space Complexity
Time Complexity: O(d * (n + k))
- d: number of digits in maximum element
- n: number of elements
- k: range of digits (0-9, so k = 10)
- Each pass: O(n + k) for Counting Sort
- Total: O(d * (n + k)) ≈ O(d * n) for integers
Space Complexity: O(n + k)
- Output array: O(n)
- Count array: O(k) = O(10) = O(1)
- Total: O(n)
Stability: Stable
- Counting Sort maintains relative order
- Important for sorting objects with multiple fields
8. When to Use Radix Sort
Best For:
- Integers with limited digit range
- When number of digits is small compared to array size
- When stability is required
- Fixed-width integers
Not Recommended For:
- Floating-point numbers (without modification)
- Strings (requires different approach)
- Very large digit ranges
- When d is large (many passes needed)
9. Important Considerations
Digit Extraction:
- (arr[i] / exp) % 10 extracts digit at position exp
- exp = 1: ones place
- exp = 10: tens place
- exp = 100: hundreds place
Stability:
- Processing from right to left (i = n-1 to 0) maintains stability
- Equal digits preserve relative order from previous pass
Number of Passes:
- Determined by maximum element's digit count
- Example: max = 802 → 3 passes
- Example: max = 9999 → 4 passes
10. return 0;
This ends the program successfully.
Summary
- Radix Sort processes digits from least to most significant.
- Uses Counting Sort as subroutine for each digit position.
- Time complexity: O(d * (n + k)) where d is number of digits.
- Space complexity: O(n + k) - requires temporary arrays.
- Stable algorithm - preserves relative order of equal elements.
- Efficient for integers with limited digit range.
- Number of passes equals number of digits in maximum element.
- Understanding Radix Sort demonstrates non-comparative sorting techniques.
This program is fundamental for learning non-comparative sorting algorithms, understanding digit-based sorting, and preparing for advanced sorting techniques in C++ programs.