Summary: In this tutorial, we will learn what is Counting Sort algorithm and how to use counting sort algorithm to sort a linear data structure like an array in C, C++, and Java.

Introduction to Counting Sort Algorithm

Counting sort is an algorithm for sorting a collection of objects according to keys that are small integers. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence.

Wikipedia

Counting Sort algorithm sorts the data structure based on the frequency of each distinct element of an array.

If stores the count of each distinct element into the relative index position of another array and then sort the array based on their index and counts.

For example, consider the following array:

Array values ranges from 2 to 15, therefore the size of the array which will store the count of distinct elements would be 15-2+1=14.

Here is the frequency of each element stored in the counting array at index position relative to their values:

The frequency of 2 is stored at index 0, frequency of 3 at 1, frequency of 4 at 2, and so on.

After storing the frequency of each element into the counting array, the algorithm rewrites the original array on the basis of the counts.

It iterates the counting array and writes the elements the number of times its frequency.

In our example, it will write 1 times 2 -> 0 times 3 -> 0 times 4 -> 1 times 5 and so on.

So the final sorted array would be:

Overall the counting sort algorithm implements the following two steps:

  1. Store the count of disting array value into another array.
  2. Iterate the counting array and rewrite the original array.

Here is the implementation of counting sort algorithm in C, C++ and, Java:

C

C++

Java

Output

2 5 8 9 10 10 11 12 15

Overview of Counting Sort

  • Counting sort is efficient to use when the array values are non-negative and lie in the small range.
  • It is not an in-place algorithm (requires an extra array i.e. counting array).
  • It has O(n)-complexity.
  • To make it a stable sort, some extra steps are needed.

In this tutorial, we learned what is counting sort algorithm and how to sort an array using counting sort algorithm in C, C++ and Java.

Leave a Reply