Navneet Singh
Navneet Singh Once a wise man said me, 'words are mighter than a sword'. Living up to the wise man wisdom.

Counting Sort | Pseudo Code | Example | Analyzing Complexity

Counting Sort | Pseudo Code | Example | Analyzing Complexity

Till now we have introduced insertion sort, merge sort, heap sort and quick sort. Out of which we know that merge sort and heap sort has a worst case of O(n*lgn) and quick sort has an average case of O(n*lgn).

Till now all the above algorithms mentioned use comparison as a medium to arrange elements in ascending or descending order. Now we are going to work on a very interesting algorithm which does not uses comparison as a medium to sort the numbers. It’s called counting sort. For a n sequence of numbers it runs in omega(n*lgn) time. Counting sort sorts the element in linear time.

In this blog post we are going to
  • Write a pseudocode for counting sort
  • Explain it via example
  • Analyze the complexity of the algorithm and write a c++ program for the same.

Getting started with counting sort

Counting sort assumes that each of the given n input elements is an integer in the range of 0 to k. This type of sorting works for positive values only. In this algorithm we are given an array A[1,2,3…n] we require an auxiliary array and sorted array. Auxiliary array has size equal to max value in the array A, and sorted array has the same size as that of array A.

Next we are going to write a pseudo code for the same.

CountingSort(A)
largestElementOfA = maxElement(A)
Let C be the auxiliary array having C[0..largestElementOfA]
Let B be the final sorted array having same size as that of A
for i = 0 to largestElementOfA
C[i] = 0
for j = 1 to A.length
C[A[j]] = C[A[j]] + 1
for k = 1 to largestElementOfA
C[A[k]] = C[A[k]] + C[A[k-1]];
for n = 1 to A.length
B[C[A[n]]] = A[n]
C[A[n]] = C[A[n]] - 1
view raw Counting Sort hosted with ❤ by GitHub
Now we have written a pseudocode for counting sort. The explanation of the algorithm can be stated via following example.

As shown in the above example we have an auxiliary array C and initially place all the value of C as 0. Next we take the elements of unsorted array A and use it as indexes for auxiliary array. Then we add the values at current position and next position of the array and use it as the index for sorted array to get our sorted array as shown in above example.

Analyzing counting sort

We have used 4 for loops however since they are used in parallel. At worst the loop is parsed through A.length which gives sorting time as θ (n) where n is A.length.

An important property of counting sort is that it is stable. Numbers with the same value appears in the output array as it appears in the input array. Normally the property of stability is important only when data are carried around with the element being sorted. Such property proves that counting sort is stable.

That’s all folks! We have seen an algorithm which sorts data in linear time only when the elements of the array are positive.