Sorting is a near ubiquitous process in our daily lives. It makes sense to organize things to better use them. The same can be said for data. In computer programming—and mathematics, for that matter—sorting algorithms are frequently used to order data as needed to perform a calculation, feed an engine, render an interface, etc.
There are several well known sorting algorithms: e.g. bubble, quick, selection, insertion, merge, heap, bucket. There is also a lesser known sorting algorithm, relegated to the proverbial annex like poor Toby: counting sort. Have you ever heard of it? It is infrequently used because it comes with some caveats which make it impractical in most use cases.
Counting sort is a sorting algorithm that sorts the elements with the technique of counting the number of occurrences of each unique element in an array or list. Counting algorithm is basically a hashing technique with the keys between a specific range and then counting the number of objects having distinct key values. Lastly, we will get the output sequence by doing some arithmetic calculation for positioning each object using their key values. Counting sort uses the partial hashing technique to count the occurrence of the element in O(1). The most important feature of working with counting sort is that it works with negative elements also. It uses the subroutine to another sorting algorithm. The counting sort is not a comparison-based sorting algorithm and its time complexity is O(n) with space proportional to the range of elements. Therefore, the efficiency of counting sort is maximum if the range of elements is not greater than the number of elements to be sorted.
Algorithm of Counting
1. Counting_Sort( array, ele ) // ele is number of elements in the array
2. max = discover the array's biggest element
3. Create a count array of maximum + 1 size and fill it with all 0s.
4. for i = 0 to ele
5. discover the total number of occurrences of each element and save the count in the count array at the index.
6. for i = 0 to max
7. Add the current(i) and previous(i-1) counts to get the cumulative sum, which you may save in the count array.
8. For j = ele down to 1
9. Decrement the count of each element copied by one before copying it back into the input array.
Implementation in Python
Implementation in C++
Counting sort takes O(n+k) time and O(n+k) space, where nn is the number of items we're sorting and k is the number of possible values. We iterate through the input items twice—once to populate counts and once to fill in the output array. Both iterations are O(n) time. Additionally, we iterate through counts once to fill in nextIndex, which is O(k) time. The algorithm allocates three additional arrays: one for counts, one for nextIndex, and one for the output. The first two are O(k) space and the final one is O(n) space.
In many cases cases, k is O(n) (i.e.: the number of items to be sorted is not asymptotically different than the number of values those items can take on. Because of this, counting sort is often said to be O(n) time and space.
With this article at Logicmojo, you must have the complete idea of analyzing Counting Sort algorithm.
Good Luck & Happy Learning!!