Radix Sort In Java

Question

• You are given an array(arr) of integers.
• You have to sort the given array in increasing order using radix sort.

Input Format

An Integer n
arr1
arr2..
n integers

Constraints

1 <= N <= 10000
0 <= arr[i] <= 10^8

Sample Input

5
7
2
4
1
3

Sample Output

After sorting on 1 place -> 1 2 3 4 7
1 2 3 4 7

Program

import java.io.*;
import java.util.*;

public class Main {

    public static void radixSort(int[] arr) {
        // write code here
        int max = Integer.MIN_VALUE;
        for(int val : arr){
            if(val > max){
                max = val;
            }
        }
        int exp = 1;
        while(exp <= max){
            countSort(arr, exp);
            exp = exp * 10;
        }
    }

    public static void countSort(int[] arr, int exp) {
        // write code here
        int[] frqa = new int[10];
        for(int i = 0; i < arr.length; i++){
            int val = arr[i] / exp % 10;
            int pos = val;
            frqa[pos]++;  
        }
        //Prefex sum array
        for(int i = 1; i < frqa.length; i++){
            frqa[i] = frqa[i] + frqa[i - 1];
        }
        int[] ans = new int[arr.length];
        for(int i = arr.length - 1; i >= 0; i--){
            int val = arr[i] / exp % 10;
            int pos = val;
            int idx = frqa[pos] - 1;
            ans[idx] = arr[i];
            frqa[pos]--;
        }
        for(int i = 0; i < arr.length; i++){
            arr[i] = ans[i];
        }
        System.out.print("After sorting on " + exp + " place -> ");
        print(arr);
    }

    public static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) throws Exception {
        Scanner scn = new Scanner(System.in);
        int n = scn.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scn.nextInt();
        }
        radixSort(arr);
        print(arr);
    }

}