Radix Sort
Radix sort is a sorting algorithm that groups digits of the same place value and then sorts the elements in increasing or decreasing order. Radix sort is a non-comparative algorithm that works on integer keys. It is less flexible than other sorting algorithms because it is based on digits or letters. Radix sort must be rewritten for each different type of data.
Radix sort can be implemented both recursively (MSD radix sort) and non-recursively (LSD radix sort). Radix sort achieves O(n) time complexity.
Here are some LeetCode problems related to radix sort:
- Maximum Gap
- Sort an Array
- Query Kth Smallest Trimmed Number
Radix Sort
Radix Sort is a sorting algorithm that sorts numbers digit by digit, from least significant digit to most significant digit. The algorithm works with integers and uses a stable sort, like counting sort or bucket sort, to sort each digit. The key takeaway is that it’s a non-comparative sorting algorithm, meaning it doesn’t compare elements directly to sort them.
Java Code for Radix Sort
In Java, you can use an array and loops to sort digits.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| import java.util.Arrays;
public class RadixSort {
public static void sort(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
int exp = 1;
int n = arr.length;
int[] temp = new int[n];
while (max / exp > 0) {
countingSortByDigit(arr, temp, exp, n);
exp *= 10;
}
}
private static void countingSortByDigit(int[] arr, int[] temp, int exp, int n) {
int[] count = new int[10];
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
temp[--count[(arr[i] / exp) % 10]] = arr[i];
}
System.arraycopy(temp, 0, arr, 0, n);
}
}
|
sort() initializes variables and calls countingSortByDigit() for each digit.countingSortByDigit() sorts numbers by a specific digit using counting sort.
C++ Code for Radix Sort
In C++, the Vector STL and loops serve the same purpose.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void countingSortByDigit(vector<int>& arr, int exp) {
int n = arr.size();
vector<int> output(n), count(10, 0);
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
void radixsort(vector<int>& arr) {
int max = *max_element(arr.begin(), arr.end());
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSortByDigit(arr, exp);
}
}
|
radixsort() finds the max element and calls countingSortByDigit().countingSortByDigit() sorts the array based on a specific digit.
Python Code for Radix Sort
Python simplifies things further, thanks to its list comprehensions.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| def counting_sort_by_digit(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for i in arr:
count[(i // exp) % 10] += 1
for i in range(1, 10):
count[i] += count[i - 1]
i = n - 1
while i >= 0:
output[count[(arr[i] // exp) % 10] - 1] = arr[i]
count[(arr[i] // exp) % 10] -= 1
i -= 1
for i in range(n):
arr[i] = output[i]
def radix_sort(arr):
max_num = max(arr)
exp = 1
while max_num // exp > 0:
counting_sort_by_digit(arr, exp)
exp *= 10
|
radix_sort() finds the maximum element and uses it to call counting_sort_by_digit().counting_sort_by_digit() performs the counting sort for each digit.
Describe the Concept of Radix Sort
Radix Sort is a non-comparative sorting algorithm. It works by distributing the individual digits of the numbers to different buckets based on each digit, starting from the least significant digit (LSD) to the most significant digit (MSD). It then collects the numbers back from the buckets. This process is repeated for every digit until the array is sorted.
Java Code for Radix Sort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public class RadixSort {
public static void sort(int[] arr) {
int max = findMax(arr);
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, exp);
}
}
private static int findMax(int[] arr) {
int max = arr[0];
for (int num : arr) {
if (num > max) {
max = num;
}
}
return max;
}
private static void countingSort(int[] arr, int exp) {
// Implementation of counting sort based on digit represented by exp
}
}
|
Here, the function findMax finds the maximum number in the array. This helps in determining the number of digits in the largest number, which dictates how many times the algorithm will loop.
C++ Code for Radix Sort
1
2
3
4
5
6
7
8
9
10
11
12
13
| #include <algorithm>
#include <vector>
void radixSort(std::vector<int>& arr) {
int max = *std::max_element(arr.begin(), arr.end());
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, exp);
}
}
void countingSort(std::vector<int>& arr, int exp) {
// Implementation of counting sort based on digit represented by exp
}
|
In C++, we use the max_element from the Standard Library to find the maximum number. The rest of the code follows the same logic as in Java.
Python Code for Radix Sort
1
2
3
4
5
6
7
8
9
10
| def radix_sort(arr):
max_num = max(arr)
exp = 1
while max_num // exp > 0:
counting_sort(arr, exp)
exp *= 10
def counting_sort(arr, exp):
# Implementation of counting sort based on digit represented by exp
pass
|
In Python, we use the built-in max() function to find the maximum number in the list. The algorithm then proceeds to sort the numbers based on each digit using counting sort.
By utilizing Radix Sort, you can achieve linear time complexity, making it efficient for sorting large datasets. However, it’s worth noting that Radix Sort is not suitable for sorting strings or negative numbers without modifications.