Radix Sort in Java
Radix sort in Java uses the digits of the numbers given in the sorted array to sort the numbers. The radix sort uses the place value of digits to do the sorting moving from the LSB (Least Significant Digit) to MSB (Most Significant Digit) of the numbers. By using the counting sort, the quick sort place elements to their appropriate position. Unlike other sorting algorithms, this sorting algorithm never compares numbers to do the sorting. Hence, radix sort is a non-comparative sorting algorithm.
Algorithm and Pseudo Code
// arr -> is the input array to sort
//dig number of digits each integer has
radixSort(arr, dig)
// Uses counting sort for dig number of passes
// Each element in the array has dig number of digits
// consider digits of every number from left to right to do the sorting
for i = 1 to dig do
int freq[] = {0, 0, 0, 0, 0, 0, 0, 0, 0 ,0};
int res[] = new int[arr.length];
// Store the frequency of “digits as keys” in freq[]
// digits as keys — the number that is present at the place i
for j = 0 to sizeOfArr do
increase freq[key of (arr[j]) in the pass i] by 1
end for
for l = 1 to 10 do
freq[l] = freq[l] + freq[l — 1]
end for
// create the resultant array by checking
// the position of arr[i] from freq[k]
for i = size — 1 down to 0 do
res[ freq[key of(arr[i])] ] = arr[j]
reduce freq[key of(arr[i])] by 1
end for
// Now the input array arr[] contains the numbers sorted in
// accordance to current digit place
for j = 0 to size do
arr[j] = res[j]
end for
end for
end radixSort
