what is Counting Sort?

Counting Sort

It is a sorting technique based on the keys i.e. objects are collected according to keys which are small integers. Counting sort calculates the number of occurrence of objects and stores its key values. New array is formed by adding previous key elements and assigning to objects.

Complexity

Time Complexity: O(n+k) is worst case where n is the number of element and k is the range of input.

Space Complexity: O(k) k is the range of input.

Complexity	Best Case	Average Case	Worst Case
Time Complexity	Ω(n+k)	θ(n+k)	O(n+k)
Space Complexity			O(k)

Limitation of Counting Sort

• It is effective when range is not greater than number of object.
• It is not comparison based complexity.
• It is also used as sub-algorithm for different algorithm.
• It uses partial hashing technique to count the occurrence.
• It is also used for negative inputs.

Algorithm

• STEP 1 START
• STEP 2 Store the input array
• STEP 3 Count the key values by number of occurrence of object
• STEP 4 Update the array by adding previous key elements and assigning to objects
• STEP 5 Sort by replacing the object into new array and key= key-1
• STEP 6 STOP

Program

1. #include <stdio.h>  
2. void counting_sort(int A[], int k, int n)  
3. {  
4.     int i, j;  
5.     int B[15], C[100];  
6.     for (i = 0; i <= k; i++)  
7.         C[i] = 0;  
8.     for (j = 1; j <= n; j++)  
9.         C[A[j]] = C[A[j]] + 1;  
10.     for (i = 1; i <= k; i++)  
11.         C[i] = C[i] + C[i-1];  
12.     for (j = n; j >= 1; j--)  
13.     {  
14.         B[C[A[j]]] = A[j];  
15.         C[A[j]] = C[A[j]] - 1;  
16.     }  
17.     printf("The Sorted array is : ");  
18.     for (i = 1; i <= n; i++)  
19.         printf("%d ", B[i]);  
20. }  
21. /*  End of counting_sort()  */  
22.    
23. /*  The main() begins  */  
24. int main()  
25. {  
26.     int n, k = 0, A[15], i;  
27.     printf("Enter the number of input : ");  
28.     scanf("%d", &n);  
29.     printf("\nEnter the elements to be sorted :\n");  
30.     for (i = 1; i <= n; i++)  
31.     {  
32.         scanf("%d", &A[i]);  
33.         if (A[i] > k) {  
34.             k = A[i];  
35.         }  
36.     }  
37.     counting_sort(A, k, n);  
38.     printf("\n");  
39.     return 0;  
40. }