Wednesday, May 31, 2017

Linear Sorting - Counting Sort

Counting Sort is a linear sorting algorithm with the time complexity O(k+n). Counting sort put some restriction on the elements we wanted to sort, i.e 0 <= ai< K. We usually take the value of k=n so that the time complexity will become O(n), i.e O(n+n)=>O(2n)=>O(n).Here we are just counting for every index of count array ‘number of elements in the given input array are less than are equals to the index of count array’.
counti  = numbers of elements less than or equals to ‘i' in input array. this is the two step process we will explain you in the example.
Example
Let's take the value of K=5 and N=10.
Input array Looks Like this
In our example we took 10 elements that is the value of N. The range we chosen is 0 to 5 that is the value of K . Values in the array are restrict to 0 <= Ai < K, for every ith index.

Construct the count array
Step-I
In first step we calculate the count of all the elements of the input array A. Then Store the result in the count array C.The way we count is depected below.
Here we traverse through array A and increase the count of array C.
A[0] = 3 , So we increase C[3] value by 1.
A[1] = 4 , So we increase C[4] value by 1.
A[2] = 2 , So we increase C[2] value by 1.
So on...As shown in above animation.
Step-II
In second step we calculate how many elements exist in the input array A which are less than or equals for the given index. Ci = numbers of elements less than or equals to i in input array.

C[0]=2 means, there are 2 elements exist in input array A which are less than are equals to 0.
C[1]=3 means, there are 3 elements exist in input array A which are less than are equals to 1.
C[2]=5 means, there are 5 elements exist in input array A which are less than are equals to 2.
Step-III
In this step we place the input array A element at sorted position by taking help of constructed count array C ,i.e what we constructed in step two. We used the result array B to store the sorted elements. Here we handled the index of B start from zero.


A[0]=3, get the sorted position for element 3, C[3]= 7, so the sorted position for 3 is 7. We place the element 3 at 7th position , i.e B[6]= 3 (we used 6 instead 7 why because indexing of B start from Zero. ) . So A[0] is sorted now and stored it in result array B. We animated the process below.


Time complexity O(K+N), if K=N then O(N).
Space complexity O(K+N), if K=N then O(N).
O(K) space for count array.
O(N) space for result array.
Java Code for Counting Sort .
package com.efficeintalgorithms.sorting;
import java.util.Scanner;
public class CountingSort {
                /*
                 * restriction on counting Sort is
                 * 'count' array depends on
                 * maximum number (i.e maxLimit) in an given input array 'a' 
                 *
                 */
                private static int k=5;
               
                public static void main(String[] args) {
                               
                                Scanner input=new Scanner(System.in);
                                System.out.println("\nEnter the Number of elements to be sorted");
                                int lengthOfArray=input.nextInt();
                                int count[]=new int[k];
                                int a[]=new int[lengthOfArray];
                                int result[]=new int[lengthOfArray];
                                System.out.println("\nEnter elements to be sorted ");
                                for(int i=0;i < lengthOfArray;i++){
                                                a[i]=input.nextInt();
                                }
                                System.out.println("\nStart Counting Sort....");
                                countingSort(a,result,count);
                                System.out.println("\nEnd Counting Sort......");
                               
                }
                public static void countingSort(int a[],int result[],int count[]){
                               
                                /*
                                 * Step-I
                                 * increase the 'count' array index by
                                 * traversing the  array 'a' .
                                 * Time Complexity is O(n)
                                 */                          
                                for(int i=0;i < a.length;i++){
                                                count[a[i]] = count[a[i]]+1;
                                }
                                /*Step-II
                                 * count number of elements less than
                                 * the index position available in array 'a'.
                                 * we mean to say is index 7 says how many elements are there less than or equals to 7.
                                 * Time Complexity id O(k).
                                 */
                                for(int i=1;i < count.length;i++){
                                                count[i] = count[i-1] + count[i];
                                }
                                /*Step-III
                                 * traverse the array 'a'
                                 * with the help of 'count'
                                 * place the value in 'result' array
                                 *
                                 * decrease the 'count' array element
                                 * as that position is stored in the 'result' array
                                 * Time Complexity is O(n)
                                 */
                                for(int i=0;i < a.length;i++){
                                                result[count[a[i]]-1]=a[i];
                                                count[a[i]]=count[a[i]]-1;
                                }
                               
                                /*Step-IV
                                 * 'result' array is in sorted position now.
                                 * print the result array
                                 * Time Complexity is O(n)
                                 */
                                for(int i=0;i < result.length;i++){
                                                System.out.print(result[i]+" ");
                                }
                               
                }

Execution
Enter the Number of elements to be sorted
10
Enter elements to be sorted
3 4 2 1 0 0 4 3 4 2
Start Counting Sort....
0 0 1 2 2 3 3 4 4 4
End Counting Sort......