Join the social network of Tech Nerds, increase skill rank, get work, manage projects...
 
  • Counting Sort

    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 279
    Comment on it

    Hi,

    This blog is to help you to understand counting sort in easiest manner, counting sort can sort the range in linear time but we have to provide the starting element and last highest element of the range (means elements in the range should be greater then or equal to starting point and should be less then or equal to limit value), extra space will be taken of order of the size of the range.

                   In Counting sort we maintain a count for each element inside our range and create a sorted range on the basis of it. Lets make it more simpler.

    For example

    Let we have our range is 2, 1, 2, 4, 0, 3, 1, 5

    int[] arr = new  int[] { 2, 1, 2, 4, 0, 3, 1, 5};

    we need an extra space to store the occurrence of every element inside the array (occurrence of 0, 1, 2, 3, 4, 5 has to be counted) so we need space of size 6 units.

    int[] count = new int[6];

    now we need to count the frequency of every element of the range and put it inside the count array.

    arr     2 1 2 4 0 3 1 5
    
    count   1 2 2 1 1 1
    
    index   0 1 2 3 4 5

    now we need to modify our count array such that in the updated array element at index i will be sum of itself and the element before it. for 1<= i < n-1.

    arr[ i ] = arr[ i ] + arr[ i - 1 ]

    now our count will be 

    count   1 3 5 6 7 8

    now from this count array we will generate our sorted array by following these steps

    we need to create a new array for the output of the size of the input range.

    int[] output = new int[8];

    traverse the elements of the input range and find the frequency of it. (first element is 2  considering it as index value for which we have count array value 5 )

    at index count[2] - 1 ( 5 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

    arr     2 1 2 4 0 3 1 5
    
    count   1 3 5 6 7 8
    
    index   0 1 2 3 4 5
    
    output  0 0 0 0 2 0 0 0 

    after reducing the count value by 1

    count   1 3 4 6 7 8

    Next element inside input is 1

    at index count[1] - 1  ( 3 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

    arr     2 1 2 4 0 3 1 5
    
    count   1 3 4 6 7 8
    
    index   0 1 2 3 4 5
    
    output  0 0 1 0 2 0 0 0 

    after reducing the count value by 1

    count   1 2 4 6 7 8

    Next element inside input is 2

    at index count[2] - 1  ( 4 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

    arr     2 1 2 4 0 3 1 5
    
    count   1 2 4 6 7 8
    
    index   0 1 2 3 4 5
    
    output  0 0 1 2 2 0 0 0 

    after reducing the count value by 1

    count   1 2 3 6 7 8

    Next element inside input is 4

    at index count[4] - 1  ( 7 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

    arr     2 1 2 4 0 3 1 5
    
    count   1 2 3 6 7 8
    
    index   0 1 2 3 4 5
    
    output  0 0 1 2 2 0 4 0 

    after reducing the count value by 1

    count   1 2 3 6 6 8

    Next element inside input is 0

    at index count[0] - 1  ( 1 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

    arr     2 1 2 4 0 3 1 5
    
    count   1 2 3 6 6 8
    
    index   0 1 2 3 4 5
    
    output  0 0 1 2 2 0 4 0

     

    after reducing the count value by 1

    count   0 2 3 6 6 8

    Next element inside input is 3

    at index count[3] - 1  ( 6 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

    arr     2 1 2 4 0 3 1 5
    
    count   0 2 3 6 6 8
    
    index   0 1 2 3 4 5
    
    output  0 0 1 2 2 3 4 0 

    after reducing the count value by 1

    count   0 2 3 5 6 8

    Next element inside input is 1

    at index count[1] - 1  ( 2 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

    arr     2 1 2 4 0 3 1 5
    
    count   0 2 3 5 6 8
    
    index   0 1 2 3 4 5
    
    output  0 1 1 2 2 3 4 0 

    after reducing the count value by 1

    count   0 1 3 5 6 8

     

    Next element inside input is 5

    at index count[5] - 1  ( 8 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

    arr     2 1 2 4 0 3 1 5
    
    count   0 1 3 5 6 8
    
    index   0 1 2 3 4 5
    
    output  0 1 1 2 2 3 4 5 

    after reducing the count value by 1

    count   0 1 3 5 6 7

     

    Program for Count sort 

    public class CountSort {
    	public static void main(String[] args) {
    		// We considered our range from 0 to 9 in this case
    		int[] arr = new int[] { 1, 4, 1, 2, 7, 5, 2 };
    		int[] count = new int[10];
    		int[] output = new int[arr.length];
    
    		System.out.print("Input array : ");
    		for (int i : arr)
    			System.out.print(i + " ");
    		System.out.println();
    
    		//stroring the count of elements inside the input array
    		for (int i : arr)
    			count[i]++;
    
    		//adding previous index value in the new updated count array
    		for (int i = 1; i < 10; i++)
    			count[i] += count[i - 1];
    
    		//puting values in output array
    		for (int i : arr) {
    			output[count[i]-1] = i;
    	        --count[i];
    		}
    
    		System.out.print("Output array: ");
    		for (int i : output)
    			System.out.print(i + " ");
    		System.out.println();
    
    	}
    }
    

    Output of the above program is

    Input array : 1 4 1 2 7 5 2 
    Output array: 1 1 2 2 4 5 7 
    

     

    Thanks :)

 0 Comment(s)

Sign In
                           OR                           
                           OR                           
Register

Sign up using

                           OR                           
Forgot Password
Fill out the form below and instructions to reset your password will be emailed to you:
Reset Password
Fill out the form below and reset your password: