Counting Sort is a type of sorting algorithm used to sort data structures with the help of counts.

Counting sort is efficient to use when:

  • values of element lie in the small range.
  • the values are non-negative.

Counting Sort Algorithm

Counting array– It is the array that stores the counts of occurrence of each value.

For example in our case:

Array values ranging from 2 to 15

Since 2 is the minimum element in the array and 15 is the maximum element so the size of the counting array will be 15-2+1=14.

Counting array will store the frequency of each element of the original array at the relative index position. For example in our case, the frequency of 2 will be stored at index 0, frequency of 3 at 1, frequency of 4 at 2 and so on.

Finally, after storing the frequency of each element in the counting array, we will rewrite the original array on the basis of the counting array. For example in our case index position 0 has 1 – it means only a single 2 was present in the original array, index position 1 has 0 – it means no 3 was present in the original array.

So All we need to do in counting sort is:

  1. Count the occurrence of value in the array and store it in counting Array.
  2. Track the counting array and rewrite the original array.

C

C++

Java

Output

Overview of Counting Sort

  • Not an in-place algorithm (requires an extra array i.e counting array).
  • O(n)-complexity.
  • To make it a stable sort, some extra steps are needed.

The basic concept is to sort the array with the help of the counts. That’s all for the counting sort program. If you face any problem then comment below.

Leave a Reply

Close Menu