Radix Sort
Radix sort is a generalization of a bucket sort. Radix sort is a linear sorting algorithm that is used to sort integers.
Radix sort performs digit sorting from the least significant to the most significant digit.
To sort decimal numbers, where the radix or base is 10, we need 10 buckets. These buckets are numbered from 0 - 9.
A radix sort works similar to sorting students' names alphabetically.
| Range | Passes |
|---|---|
| 0 to 99 | 2 Passes |
| 0 to 999 | 3 Passes |
| 0 to 9999 | 4 Passes |
| 0 to 99999 | 5 Passes |
- For the first pass, numbers are sorted by least significant digit. Numbers with same least significant digit are stored in the same bucket.
- In the second pass, numbers are sorted by the second least significant digit.
- The numbers in buckets are merged at the end of every pass to produce a common list.
- Number of passes depends on the range of numbers being sorted.
Time Complexity
| Case | Time Complexity |
|---|---|
| Best Case | Ω (n + k) |
| Average Case | θ (n k) |
| Worst Case | O (n k) |
- Best Case Ω (n + k):It occurs when there is no sorting needed, i.e. the array is already sorted.
- Average Case θ (n k): The array elements are in a jumbled order that is not properly ascending and descending.
- Worst Case O (n k): This occurs when the array elements need to be sorted in reverse order.
Space Complexity
| Space Complexity | O(n + k) |
| Stable | Yes |
- The space complexity of radix sorting is
O (n + k).
Radix Sort
#include <stdio.h>
int getMax(int a[], int n) {
int max = a[0];
for(int i = 1; i<n; i++) {
if(a[i] > max)
max = a[i];
}
//maximum element from the array
return max;
}
// function to implement counting sort
void countingSort(int a[], int n, int place) {
int output[n + 1];
int count[10] = {0};
// Calculate count of elements
for (int i = 0; i < n; i++)
count[(a[i] / place) % 10]++;
// Calculate cumulative frequency
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
// Place the elements in sorted order
for (int i = n - 1; i >= 0; i--) {
output[count[(a[i] / place) % 10] - 1] = a[i];
count[(a[i] / place) % 10]--;
}
for (int i = 0; i < n; i++)
a[i] = output[i];
}
// function to implement radix sort
void radix_sort(int a[], int n) {
// get maximum element from array
int max = getMax(a, n);
// Apply counting sort to sort elements based on place value
for (int place = 1; max / place > 0; place *= 10)
countingSort(a, n, place);
}
// function to print array elements
void print(int a[], int n) {
for (int i = 0; i < n; ++i)
printf("%d ", a[i]);
printf("\n");
}
int main() {
int a[] = {11, 289, 380, 222, 145, 920, 514, 777, 122};
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
print(a,n);
radix_sort(a, n);
printf("After applying Radix sort, the array elements are - \n");
print(a, n);
} class RadixSort {
static int getMax(int a[], int n) {
int max = a[0];
for(int i = 1; i<n; i++) {
if(a[i] > max)
max = a[i];
}
//maximum element from the array
return max;
}
// function to implement counting sort
static void countingSort(int a[], int n, int place) {
int[] output = new int[n+1];
int[] count = new int[10];
// Calculate count of elements
for (int i = 0; i < n; i++)
count[(a[i] / place) % 10]++;
// Calculate cumulative frequency
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
// Place the elements in sorted order
for (int i = n - 1; i >= 0; i--) {
output[count[(a[i] / place) % 10] - 1] = a[i];
count[(a[i] / place) % 10]--;
}
for (int i = 0; i < n; i++)
a[i] = output[i];
}
// function to implement radix sort
static void radixSort(int a[], int n) {
// get maximum element from array
int max = getMax(a, n);
// Apply counting sort to sort elements based on place value
for (int place = 1; max / place > 0; place *= 10)
countingSort(a, n, place);
}
// function to print array elements
static void print(int a[], int n) {
for (int i = 0; i < n; ++i)
System.out.print(a[i] + " ");
}
public static void main(String args[]) {
int a[] = {11, 289, 380, 222, 145, 920, 514, 777, 122};
int n = a.length;
System.out.print("Before sorting array elements are - \n");
print(a, n);
radixSort(a, n);
System.out.print("\n\nAfter applying Radix sort, the array elements are - \n");
print(a, n);
}
}