### Radix Sort Algorithm - The Coding Shala

In this post, we will learn what is Radix Sort Algorithm and how to implement Radix Sort in Java.

## Radix Sort Algorithm

As we know sorting algorithms like Merge sort, Quicksort, etc is works in O(N log N) time. They can not do better than NlogN. We have another option as Counting sort that works in a linear time O(n+k) but the limitation in the range is there.

We use the Radix sort algorithm when we have elements in the range from 1 to n^2. In the Radix sort algorithm, we do digit by digit sort starting from least significant digit(leftmost) to most significant digit(rightmost). We use counting sort to sort the digits because the range of these digits is less in the range of 0 to 9.

### Working of Radix Sort Algorithm

Here is what the array looks like after the one's place sorting:

after sorting-> { 173, 324, 4, 134, 127, 217, 38 }

Another reason for using counting sort here is counting sort algorithm is comes in a stable sorting algorithm. A stable sorting algorithm is if two values are the same in the array then they come in the same order after sorting the array.

Now, we will sort the array on the ten's place:

after sorting-> { 04, 217, 324, 127, 134, 38, 173 }

### Time Complexity of Radix Sort Algorithm

In Radix sort, we use counting sort that takes O(n+k) time and space and we do it for every digit of the item so Radix sort takes O(d*(n+k)) time.

So we can say that the radix sort algorithm works on O(n) time.

## Radix Sort Algorithm Java Program

**Java Program: **

//counting sort //the coding shala class Main{ public static void counting_sort(int[] input, int exp) { int len = input.length; //range is 0 to 9(inclusive) int[] output = new int[len]; int[] counts = new int[10]; //step 1 count the numbers of element for(int i=0;i<len;i++) { int last_digit = (input[i]/exp)%10; counts[last_digit]++; } //modify the count array to get index to sort the array for(int i=1; i<counts.length; i++) { counts[i] += counts[i-1]; } //now take the index from counts array //insert at index in output array //decrease the value by 1 in counts array // To make it stable we are operating in reverse order. for(int i=len-1; i>=0; i--) { int ele = input[i]; int last_digit = (ele/exp)%10; int index = counts[last_digit]; output[index-1] = ele; counts[last_digit]--; } //insert back to original array for(int i=0; i<len;i++) { input[i] = output[i]; } } public static void radix_sort(int[] input) { //first find out the max number int max = input[0]; for(int i=1; i<input.length; i++) { if(input[i]>max) max = input[i]; } //now we will sort array based on each digits for(int exp = 1; max/exp > 0; exp = exp*10) { counting_sort(input, exp); } } public static void main(String[] args) { int[] input = { 127, 324, 173, 4, 38, 217, 134}; int len = input.length; radix_sort(input); for(int i=0;i<len;i++) { System.out.print(input[i]+" "); } } }

**Other Posts You May Like**

- Quick Sort Algorithm
- Merge Sort Algorithm
- Insertion Sort Algorithm
- Counting Sort Algorithm
- Bucket Sort Algorithm

## Comments

## Post a Comment