Counting Sort – Explanation, Pseudocode and Implementation
Counting Sort is a linear sorting algorithm with asymptotic complexity O(n+k), which was found by Harold Seward in 1954.
Counting Sort is very time efficient and stable algorithm for sorting. Unlike bubble sort and merge sort, counting sort is not a comparison based algorithm. It avoids comparisons and exploits the O(1) time insertions and lookup in an array.
Counting Sort algorithm works on the keys that are small integer and lies between a specific range. It functions by counting the number of objects that have each distinct key value. Then it uses some arithmetic calculation to place each key value into a sorted sequence.
Its running time is O(Maximum key value – Minimum key value) which is linear. So it is useful only when a difference is not large.
Here are some key points of counting sort algorithm –
- Counting Sort is a linear sorting algorithm.
- Time complexity of Counting Sort is O(n+k), where n is the size of the sorted array and k is the range of key values.
- It is not an in-place sorting algorithm as it requires extra additional space O(k).
- Counting Sort is stable sort as relative order of elements with equal values is maintained.
- Counting Sort is inefficient if the range of key value (k) is very large. If the input array is already sorted then also it will require an additional array to store the sorted elements and will process it completely.
- Counting Sort has a disadvantage that it can only sort discrete values like integer, as frequency range cannot be constructed for other values.
Let’s understand it with an example –
Observe each step in the video below carefully and try to visualize the concept of this algorithm.
Pseudocode of Counting Sort
CountingSort(A) //A[]-- Initial Array to Sort //Complexity: O(k) for i = 0 to k do c[i] = 0 //Storing Count of each element //Complexity: O(n) for j = 0 to n do c[A[j]] = c[A[j]] + 1 // Change C[i] such that it contains actual //position of these elements in output array ////Complexity: O(k) for i = 1 to k do c[i] = c[i] + c[i-1] //Build Output array from C[i] //Complexity: O(n) for j = n-1 downto 0 do B[ c[A[j]]-1 ] = A[j] c[A[j]] = c[A[j]] - 1 end func
Asymptotic Analysis of Counting Sort
In this algorithm, the initialization of the count array and the loop which performs a prefix sum on the count array takes O(k) time. And other two loops for initialization of the output array takes O(n) time. Therefore, the total time complexity for the algorithm is : O(k)+ O(n)+ O(k)+ O(n)= O(n+k).
Worst Case Time complexity: O (n+k)
Average Case Time complexity: O(n+k)
Best Case Time complexity: O(n+k)
Space Complexity: O(k)
Data Structure: Array
Sorting In Place: No
Stable: Yes
Implementation of Counting Sort in C and Java programming language
C
/* C implementation Counting Sort */
#include <stdio.h>
/* Counting sort function */
void counting_sort(int A[], int k, int n)
{
int i, j;
int B[n], C[k+1];
//Initializing counting array C[i] to 0
for (i=0; i<=k; i++)
C[i] = 0;
//Store count of each element in array C
for (j=0; j<n; j++)
C[A[j]] = C[A[j]] + 1;
/* Change C[i] such that it contains actual
position of these elements in output array*/
for (i=1; i<k+1; i++)
C[i] = C[i] + C[i-1];
//Creating Output array from C[i]
//and decrementing value of C[i].
for (j=n-1; j>=0; j--)
{
B[C[A[j]]-1] = A[j];
C[A[j]] = C[A[j]] - 1;
}
//Printing sorted array
printf("The Sorted array is : ");
for (i=0; i<n; i++)
printf("%d ", B[i]);
}
/* The main() begins */
int main()
{
int n, max = 0,i;
printf("Enter the number of input : ");
scanf("%d", &n);
int A[n];
printf("\nEnter the elements to be sorted :\n");
/*Storing element in a array.
And finding max of elements to set range
of counting array C[]*/
for (i=0; i<n; i++)
{
scanf("%d", &A[i]);
if (A[i] > max) {
max= A[i];
}
}
//calling counting-sort function
counting_sort(A, max, n);
printf("\n");
return 0;
}
JAVA
/* Java implementation Counting Sort */
package codingeek;
import java.util.Arrays;
import java.util.Scanner;
public class CountSort {
/* Counting sort function */
void countingSort(int A[] , int max){
int n= A.length ;
int B[]=new int[n];
int C[]=new int[max+1];
//Initializing counting array C[] to 0
for (int i=0; i <=max; i++)
C[i] = 0;
//Storing count of each element in array C
for (int j=0; j<n; j++)
C[A[j]] = C[A[j]] + 1;
/* Change C[i] such that it contains actual
position of these elements in output array*/
for (int i=1; i<max+1; i++)
C[i] = C[i] + C[i-1];
//Creating Output array from C[i]
//and decrementing value of C[i].
for (int j=n-1; j>=0; j--)
{
B[C[A[j]]-1] = A[j];
C[A[j]] = C[A[j]] - 1;
}
//Printing sorted array
System.out.println("The Sorted array is : ");
//print sorted array
System.out.println(Arrays.toString(B));
}
public static void main (String args[]){
@SuppressWarnings("resource")
Scanner sc=new Scanner(System.in);
System.out.println("Enter the number of input : ");
int n= sc.nextInt();
int A[] =new int[n];
int max=0;
System.out.println("Enter the elements to be sorted :");
/*Storing element in a array.
And finding max of elements to set range
of counting array C[]*/
for(int i=0; i<n; i++){
A[i]=sc.nextInt();
if (A[i] > max) {
max= A[i];
}
}
CountSort ob= new CountSort();
//calling counting-sort function
ob.countingSort(A, max);
}
}
Counting Sort is one of the most efficient and a stable algorithm for sorting. It is simple to understand and easy to implement. A good programmer must know this linear sorting algorithm. This is also a hot topic in many beginner and algorithm based interviews.
Some other Linear Sorting Algorithms are: Bucket Sort and Radix Sort.(Will be discussed in future posts)
Radix Sort can handle larger keys more efficiently as compare to Counting Sort.
Knowledge is most useful when liberated and shared. Share this to motivate us to keep writing such online tutorials for free and do comment if anything is missing or wrong or you need any kind of help.
Do not forget to SHARE and SUBSCRIBE.
Keep Learning… Happy Learning.. 🙂