Java Tutorial

# Java Program for Radix Sorting

## What is radix sort ?

Radix sort is the generalized bin sort.

Radix sort key idea is to bin sort all the array elements, first on f(k) (the least significant digit, then concentrate bins for the lowest value first, again bin sort on f(k-1) digit and so on.

Make sure each array element is appended to the end of the list, not the beginning.

Sort the array elements using counter range(0 to 9) based on least digit value.

Repeat the sorting for next digits till maximum element number digits.

Radix sorting time complexity is O(N∗logb(N)). here N is the number of elements in the list, b is the base for representing numbers.

```import java.util.Scanner;

public static int max(int[] listVals){
int maxVal = listVals[0];
for(int i=1; i<listVals.length;i++){
if(maxVal<listVals[i]){
maxVal = listVals[i];
}
}
return maxVal;
}
public static void countingSort(int[] listVals, int n, int place){
int integerRange = 10;
int[] freq = new int[integerRange];
for(int i=0;i<integerRange;i++){
freq[i] = 0;
}
int[] listSorted = new int[n];
for(int i=0;i<n;i++){
listSorted[i]=0;
}
for(int i=0;i<n;i++){
freq[(listVals[i]/place)%integerRange] += 1;
}
for(int i=1;i<integerRange;i++){
freq[i] += freq[i-1];
}
int i = n-1;
while(i>=0){
listSorted[freq[(listVals[i]/place)%10]-1]=listVals[i];
freq[(listVals[i]/place)%10] -= 1;
i -= 1;
}
for(int j=0;j<n;j++){
listVals[j] = listSorted[j];
}
}

int n = listVals.length;
int maxVal = max(listVals);
int mulVal = 1;
while(maxVal>0){
countingSort(listVals, n, mulVal);
mulVal *= 10;
maxVal /= 10;
}
}

public static void main(String[] args){
int[] numberList, sortedList;
Scanner in = new Scanner(System.in);
System.out.println("--------------------");
System.out.println("Enter numbers count: ");
int count = in.nextInt();
numberList = new int[count];
System.out.println("Enter numbers: ");
for (int i=0;i<count;i++){
numberList[i]=in.nextInt();
}
in.close();

System.out.println("Sorted numbers: ");
for(int number : numberList){
System.out.print(number+"\t");
}
}
}
```
Output:
```\$ javac RadixSortingTest.java
--------------------
Enter numbers count:
5
Enter numbers:
2
3
1
5
4
Sorted numbers:
1	2	3	4	5
```

Java Tutorial