A Non-Comparative Sorting Algorithm: Counting Sort

Counting sort is a non-comparative sorting algorithm that is efficient. In the counting sort algorithm, it counts the number of occurrences of every unique element in the array. These number of occurrences will then be stored in a count array. The counting sort algorithm is best utilized if the range of the elements is smaller than the number of elements to be sorted.

Referring to the picture below, the counting sort algorithm is applied.

To apply the counting sort algorithm, the first step is to determine the range of the elements in the inputArray. Based on the example, the range of the elements is 5, starting from 0. To explain the example, the numbers above the boxes are the indices. So in the count array, there will be 6 indices. The second step is to count how frequently each of the elements is repeated. This part is not shown in the example. So with the inputArray of [2,5,3,0,2,3,0,3], element 2 is repeated twice, element 5 is not repeated, 3 is repeated three times, and 0 is repeated twice. These elements will be the basis for the indices of the range. So if the range of the elements is in the order of [0,1,2,3,4,5], its frequency is [2,0,2,3,0,1]. Take note of the frequency, as it will be the basis for the third step.

For the third step, which is shown in the example, the countArray. In the countArray, the frequency was added to each other, determining the cumulative count. Since 2 is the first count, it will be retained, 2 added by 0 is equal to 2, then 2 is added by 2, which will become 4. Next is add 4 by 3 resulting in 7, 7 is then added by 0, still resulting in 7, and finally, 7 is added to 1, resulting in 8. Hence, the countArray has the values of [2,2,4,7,7,8].

For the fourth step, look for the rightmost element in the inputArray, then find the number corresponding to the index in the countArray. Based on the example, since 3 is the rightmost element in the array, the one in the index 3 in the countArray will be considered. So in the index 3 of the countArray, there is an element of 7. This 7 will be subtracted by 1, becoming 6. 6 will now be the placement or the index of the element in the final outputArray. So, element 3 from the inputArray will be in the index 6 or the seventh element in the outputArray.

Finally, these steps will be repeated until all elements in the inputArray, note to start from the right, will be find their correct position in the outputArray.

The counting sort algorithm has a time complexity of (n+k), where n is the number of elements in the input array, and k is the range of the input values. This algorithm has a linear time complexity due to the constant number of operations done to each element. The space complexity for the counting sort algorithm is k due to the k+1 requirement of the count array to store the frequencies of the elements.

The counting sort algorithm is best used in non-negative integers that have a small range. The process will be more efficient if the range of the inputted values is smaller than the number of elements to be sorted. Furthermore, there are use cases and examples for the counting sort algorithm are:
Sorting the grades of students since the grading scale is limited to 0 to 100.
Sorting the word frequency where the range of frequencies is smaller than the amount of unique words in a document
Finally, sorting a list of integers within a known range.

Overall, the counting sort algorithm is an efficient and non-comparative sorting algorithm best suited for situations that have a smaller range of values compared to the number of elements to be sorted. If efficiency is what matters in a program, using the counting sort algorithm where there are no negative integers becomes an option to be utilized.

Posted using Honouree