Count Sort In Java

Question

• You are given an array(arr) of integers.
• You have to sort the given array in increasing order using count 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

-2
1
3
4
7

Program

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

public class Main {

  public static void countSort(int[] arr, int min, int max) {
   //write your code here
   int[] frqa = new int[max - min + 1];
   
   for(int i = 0; i < arr.length; i++){
       int val = arr[i];
       int pos = val - min;
       frqa[pos]++;
   }
   
   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];
       int pos = val - min;
       int idx = frqa[pos] - 1;
       ans[idx] = val;
       frqa[pos]--;
   }
   for(int i = 0; i < arr.length; i++){
       arr[i] = ans[i];
   }
  }

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

  public static void main(String[] args) throws Exception {
    Scanner scn = new Scanner(System.in);
    int n = scn.nextInt();
    int[] arr = new int[n];
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
      arr[i] = scn.nextInt();
      max = Math.max(max, arr[i]);
      min = Math.min(min, arr[i]);
    }
    countSort(arr,min,max);
    print(arr);
  }

}