Counting Sort Algorithm | C and C++ Implementation

Given a collection of n items, each of which has a non-negative integer key whose maximum value is at most k, effectively sort it using counting sort algorithm.

 
Counting sort is an integer-based sorting algorithm for sorting an array whose keys lies between a specific range. It counts the number of elements that have each distinct key value and then use those counts to determine the positions of each key value in the output.

Counting sort can be used to find most frequent letter in a file or sort an limited range array efficiently. It is often used as a subroutine in radix sort sorting algorithm, and because of this, it is important for counting sort to be a stable sort.

 

Algorithm:

The algorithm loops over the items, computing a histogram of the number of times each key occurs within the input collection. It then performs a prefix sum computation to determine, for each key, the starting position in the output array of the items having that key. Finally, it loops over the items again, moving each item into its sorted position in the output array. In below code:

  1. After the first for loop, freq[i] stores the number of items with key equal to i.
     
  2. After the second for loop, it instead stores the number of items with key less than i, which is the same as the first index at which an item with key i should be stored in the output array.
     
  3. Throughout the third loop, freq[i] always stores the next position in the output array into which an item with key i should be stored, so each item is moved into its correct position in the output array.
     

Download   Run Code

Output:

1 1 2 2 4 4 10 10 10

 
Unlike other sorting algortihms like Insertion sort, Selection sort, Merge Sort, QuickSort, etc, Counting sort is not a comparison sort as it uses key values as indices into an array as evident from above code.

 
Below is the simpler version of counting sort that doesn’t produces a stable sort. i.e. the relative order of items with equal keys is not preserved anymore.

 

Download   Run Code

Output:

1 1 2 2 4 4 10 10 10

 

Performance:

 
The time complexity of counting sort is O(n + k) where k is the range of the input and n is the size of the input. Since it uses arrays of length k + 1 and n, the total space used by the algorithm is also
O(n + k). Counting sort can be highly space-efficient when range of keys k is significantly less than the number of items n, but when variation in keys is significantly greater than the number of items
k >> n, counting sort consumes a lot of space.
 

 

C++ implementation:

 
Below is C++ implementation of counting sort that uses a std::map in place of arrays. This will definately save some space upto O(k) but increases time complexity to O(nlog(k)).

 

Download   Run Code

Output:

1 1 2 2 4 4 10 10 10 40 40

 
Exercise:

1. Extend the C solution to handle negative integers.

2. Provide the exact range of keys by calculating the difference between the maximum and minimum key values.

 
References: https://en.wikipedia.org/wiki/Counting_sort

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz