Java Program to Implement Counting Sort

«
»
This is a Java Program to implement Counting Sort Algorithm. This program is to sort a list of numbers.
Here is the source code of the Java program to implement Counting Sort Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /**
  2.  ** Java Program to Implement Counting Sort
  3.  **/
  4.  
  5. import java.util.Scanner;
  6.  
  7. /** Class CountingSort **/
  8. public class CountingSort 
  9. {
  10.     private static final int MAX_RANGE = 1000000;
  11.     /** Counting Sort function **/
  12.     public static void sort( int[] arr )
  13.     {
  14.         int N = arr.length;
  15.         if (N == 0)
  16.             return;
  17.         /** find max and min values **/
  18.         int max = arr[0], min = arr[0];
  19.         for (int i = 1; i < N; i++)
  20.         {
  21.             if (arr[i] > max)
  22.                 max = arr[i];
  23.             if (arr[i] < min)
  24.                 min = arr[i];
  25.         }
  26.         int range = max - min + 1;
  27.  
  28.         /** check if range is small enough for count array **/
  29.         /** else it might give out of memory exception while allocating memory for array **/
  30.         if (range > MAX_RANGE)
  31.         {
  32.             System.out.println("\nError : Range too large for sort");
  33.             return;
  34.         }
  35.  
  36.         int[] count = new int[range];
  37.         /** make count/frequency array for each element **/
  38.         for (int i = 0; i < N; i++)
  39.             count[arr[i] - min]++;
  40.         /** modify count so that positions in final array is obtained **/
  41.         for (int i = 1; i < range; i++)
  42.             count[i] += count[i - 1];
  43.         /** modify original array **/
  44.         int j = 0;
  45.         for (int i = 0; i < range; i++)
  46.             while (j < count[i])
  47.                 arr[j++] = i + min;
  48.     }    
  49.     /** Main method **/
  50.     public static void main(String[] args) 
  51.     {
  52.         Scanner scan = new Scanner( System.in );        
  53.         System.out.println("Counting Sort Test\n");
  54.         int n, i;
  55.         /** Accept number of elements **/
  56.         System.out.println("Enter number of integer elements");
  57.         n = scan.nextInt();
  58.         /** Create integer array on n elements **/
  59.         int arr[] = new int[ n ];
  60.         /** Accept elements **/
  61.         System.out.println("\nEnter "+ n +" integer elements");
  62.         for (i = 0; i < n; i++)
  63.             arr[i] = scan.nextInt();
  64.         /** Call method sort **/
  65.         sort(arr);
  66.         /** Print sorted Array **/
  67.         System.out.println("\nElements after sorting ");        
  68.         for (i = 0; i < n; i++)
  69.             System.out.print(arr[i]+" ");            
  70.         System.out.println();                     
  71.     }    
  72. }

advertisement
Counting Sort Test
 
Enter number of integer elements
20
 
Enter 20 integer elements
54 67 13 24 76 37 97 10 67 24 6 28 5 19 63 1 71 83 97 24
 
Elements after sorting
1 5 6 10 13 19 24 24 24 28 37 54 63 67 67 71 76 83 97 97

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.