This tutorial shows how to write Radix sort program in Java. Radix sort is also one of the linear sort algorithm which runs in O(n) time like Counting sort and Bucket sort making Radix sort faster than Quick sort or Merge sort which run in O(n*logn) time.
Radix sort algorithm
Radix sort works by doing the sorting in passes moving from least significant digit to most significant digit. Radix sort also uses buckets, in each pass you need to get digit of the number based on the pass (1s place, 10s place etc.) and store those digits in buckets. In each pass you can use a stable sort like Counting sort to sort the numbers on the digit.
Steps for the Radix sort algorithm can be summarized as follows-
- Get the maximum number in the input array.
- Iterate each digit of the maximum number starting from the least significant digit i.e. unit place moving towards the most significant digit.
- For each element in the array get the digit at that position and store it in the bucket array.
- Sort input array elements as per the digits in that pass.
- Move to next digit and repeat from step 3.
For example if input array is as- [40, 25, 206, 65, 457, 4, 81, 74, 58, 6] then the maximum number is 457 in the array so there are going to be 3 passes for 1, 10 and 100 place.
These passes and the process that is followed for Radix sort is showed in the following images.
Radix Sort Java program
public class RadixSort {
public static void main(String[] args) {
int[] arr = {40, 25, 206, 65, 457, 4, 81, 74, 58, 6};
System.out.println("Original Array- " + Arrays.toString(arr));
radixSort(arr);
System.out.println("Sorted array after Radix sort- " + Arrays.toString(arr));
}
private static void radixSort(int[] arr){
//get max element in array
int max = getMaxElementInArray(arr);
int position = 1;
// move from least significant digit
// to most significant digit
while(max/position > 0){
countingSort(arr, position);
position *= 10;
}
}
private static int getMaxElementInArray(int[] arr){
int max = arr[0];
for(int i = 1; i < arr.length; i++){
if (arr[i] > max){
max = arr[i];
}
}
return max;
}
// Counting sort used to sort array in each pass
private static void countingSort(int[] arr, int position){
int n = arr.length;
int[] output = new int[n];
int[] count = new int[n];
//Calculate frequency of each element, put it in count array
for(int i = 0; i < arr.length; i++){
count[(arr[i]/position)%10]++;
}
// Modify count array to get the final position of elements
for(int i = 1; i < n; i++){
count[i] = count[i] + count[i-1];
}
// Add elements to output array for this pass
for(int i = n-1; i >=0; i--){
output[count[(arr[i]/position)%10] - 1] = arr[i];
count[(arr[i]/position)%10]--;
}
// Copy output array to the input for
// the next pass of counting sort
for(int i = 0; i < output.length; i++){
arr[i] = output[i];
}
System.out.println("Array after Counting sort at position " + position
+ " " + Arrays.toString(arr));
}
}
Output
Original Array- [40, 25, 206, 65, 457, 4, 81, 74, 58, 6] Array after Counting sort at position 1 [40, 81, 4, 74, 25, 65, 206, 6, 457, 58] Array after Counting sort at position 10 [4, 206, 6, 25, 40, 457, 58, 65, 74, 81] Array after Counting sort at position 100 [4, 6, 25, 40, 58, 65, 74, 81, 206, 457] Sorted array after Radix sort- [4, 6, 25, 40, 58, 65, 74, 81, 206, 457]
Radix sort time and space complexity
We know that the time complexity of Counting sort is O(n+k). In Radix sort counting sort is used in each pass and the passes we have is equal to the digits in the maximum number. If digits are represented by d then the time complexity of Radix sort is O(d*(n+k)).
Space requirement is also same as the space complexity of counting sort. Count array having space k and the output array which has the same size as input array is required. Thus the space complexity of Radix sort is O(n+k).
That's all for the topic Radix Sort Java Program. If something is missing or you have something to share about the topic please write a comment.
You may also like
No comments:
Post a Comment