Java Program - Radix Sort
Radix sort is based on the idea that the sorting of the input data is done digit by digit from least significant digit to most significant digit and it uses counting sort as a subroutine to perform sorting. Counting sort is a linear sorting algorithm with overall time complexity Θ(N+K) in all cases, where N is the number of elements in the unsorted array and K is the range of input data. The idea of radix sort is to extend the counting sort algorithm to get a better time complexity when K goes up.
Example:
To understand the radix sort, lets consider an unsorted array A = [101, 1, 20, 50, 9, 98, 27, 153, 35, 899] and discuss each step taken to sort the array in ascending order.
Step 1: According to the algorithms, the input data is first sorted based on least significant digit. Therefore, array A[ ] is sorted based on one's digit. After sorting it on one's digit it will become [20, 50, 101, 1, 153, 35, 27, 98, 9, 899].
Step 2: In this step, the array A[ ] array is sorted based on ten's digit and after this step it will become [101, 1, 9, 20, 27, 35, 50, 153, 98, 899].
Step 3: Finally, the array A[ ] is sorted based on hundred's digit (most significant digit) and the array will be sorted after this step and the final array will be [1, 9, 20, 27, 35, 50, 98, 101, 153, 899].
Implementation of Radix Sort
public class MyClass { // function for radix sort static void radixsort(int Array[]) { int n = Array.length; int max = Array[0]; //find largest element in the Array for (int i=1; i<n; i++) { if(max < Array[i]) max = Array[i]; } //Counting sort is performed based on place. //like ones place, tens place and so on. for (int place = 1; max/place > 0; place *= 10) countingsort(Array, place); } static void countingsort(int Array[], int place) { int n = Array.length; int[] output = new int[n]; //range of the number is 0-9 for each place considered. int[] freq = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; //count number of occurrences in freq array for(int i = 0; i < n; i++) freq[(Array[i]/place)%10]++; //Change count[i] so that count[i] now contains actual //position of this digit in output[] for (int i = 1; i < 10; i++) freq[i] += freq[i - 1]; //Build the output array for (int i = n - 1; i >= 0; i--) { output[freq[(Array[i]/place)%10] - 1] = Array[i]; freq[(Array[i]/place)%10]--; } //Copy the output array to the input Array, Now the Array will //contain sorted array based on digit at specified place for (int i = 0; i < n; i++) Array[i] = output[i]; } // function to print array static void PrintArray(int Array[]) { int n = Array.length; for (int i=0; i<n; i++) System.out.print(Array[i] + " "); System.out.println(); } // test the code public static void main(String[] args) { int[] MyArray = {101, 1, 20, 50, 9, 98, 27, 153, 35, 899}; System.out.println("Original Array"); PrintArray(MyArray); radixsort(MyArray); System.out.println("\nSorted Array"); PrintArray(MyArray); } }
The above code will give the following output:
Original Array 101 1 20 50 9 98 27 153 35 899 Sorted Array 1 9 20 27 35 50 98 101 153 899
Time Complexity:
The time complexity of radix sort is Θ((N+b)*logb(max)) in all cases, where:
- N is the number of elements in unsorted array.
- b is the base of input array, for example, for decimal system, b is 10.
- max is the maximum element of the input array.
Recommended Pages
- Java Program - To Check Prime Number
- Java Program - Bubble Sort
- Java Program - Selection Sort
- Java Program - Maximum Subarray Sum
- Java Program - Reverse digits of a given Integer
- Java - Swap two numbers
- Java Program - Fibonacci Sequence
- Java Program - Insertion Sort
- Java Program - Find Factorial of a Number
- Java Program - Find HCF of Two Numbers
- Java Program - Merge Sort
- Java Program - Shell Sort
- Stack in Java
- Queue in Java
- Java Program - Find LCM of Two Numbers
- Java Program - To Check Whether a Number is Palindrome or Not
- Java Program - To Check Whether a String is Palindrome or Not
- Java Program - Heap Sort
- Java Program - Quick Sort
- Java - Swap Two Numbers without using Temporary Variable