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
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.
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 .
|
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......
