Counting Sort in java

Counting sort is special sorting technique used to sort elements between specific range. Lets say elements belong to range 1 to K , then Counting sort can be used to sort elements in O(N) times.
Basic idea of counting sort to find number of elements less than X, so X can be put to its correct position.

Steps for Counting Sort:

  • Take an array to store count of each elements. Lets say array elements contain 1 to K then initialize count array with K.
  • Now add elements of count array, so each elements store summation of its previous elements.
  • Modified count array stores position of elements in actual sorted array.
  • Iterate over array and put element in correct sequence based on modified count array and reduce the count by 1.

Java program for counting sort:

package org.arpit.java2blog;

import java.util.Arrays;

public class CountingSortMain {

 public static void main(String[] args) {
  System.out.println("Before Sorting : ");
  int arr[]={1,4,7,3,4,5,6,3,4,8,6,4,4};
  System.out.println(Arrays.toString(arr));
  arr=countingSort(arr);
  System.out.println("=======================");
  System.out.println("After Sorting : ");
  System.out.println(Arrays.toString(arr));
 }

    static int[] countingSort(int arr[])
    {
        int n = arr.length;
 
        // The result will store sorted array
        int result[] = new int[n];
 
       // Initialize count array with 9 as array contains elements from range 1 to 8.
        int count[] = new int[9];
        for (int i=0; i<9; ++i)
            count[i] = 0;
 
        // store count of each element in count array
        for (int i=0; i<n; ++i)
            ++count[arr[i]];
 
        // Change count[i] so that count[i] now contains actual
        // position of this element in output array
        for (int i=1; i<=8; ++i)
            count[i] += count[i-1];
 
        for (int i = 0; i<n; ++i)
        {
         result[count[arr[i]]-1] = arr[i];
            --count[arr[i]];
        }

        return result;
    }
   
}
When you run above program, you will get below output:
Before Sorting : 
[1, 4, 7, 3, 4, 5, 6, 3, 4, 8, 6, 4, 4]
=======================
After Sorting : 
[1, 3, 3, 4, 4, 4, 4, 4, 5, 6, 6, 7, 8]
Time Complexity= O(N)
I would suggest to try to debug the program to understand it better.

Written by Arpit:

If you have read the post and liked it. Please connect with me on Facebook | Twitter | Google Plus

 

Java tutorial for beginners Copyright © 2012