About Counting Sort

About “Counting Sort”

In preparation for a coding test, I’ve been studying algorithms, and in this article, I’d like to summarize the counting sort.

What is Counting Sort?

Counting sort is one of the fastest performing sorting algorithms.

It can effectively sort on data that can be represented as integers or whole numbers.

Unlike other sorting algorithms, Counting Sort has linear time complexity with no comparisons, and it shines when the range of input data is limited.

How does counting sort work?

• Counting: Counts each element of the input array, creating a count array that records the frequency of each element.
• Cumulative Count: Updates the elements in each count array with the sum of the current element and the previous element. This step determines where each element will be placed in the sorted array.
• Sorting: Traverses the input array, placing each element in a position sorted by the frequency of that element. It handles duplicate elements by updating the counts array.

Example

The array we want to sort is [3, 5, 6, 3, 1, 1].

• Counting: Creates a count array by traversing the input array and counting the frequency of each element.
• Count array: [0, 2, 0, 2, 0, 1, 1, 1]
• Cumulative Count: Generates a cumulative count array.
• Cumulative count array: [0, 2, 2, 4, 4, 4, 5, 6].
• Sorting: Now traverses the original array, placing each element at its position.
• Sorted array: [1, 1, 3, 3, 5, 6]

Conclusion

Counting sort is a fast sorting algorithm that provides performance that is proportional to the range of the input data.

It is especially useful when the range of the data is small and can be represented as an integer.

Its ability to sort without comparison is one of the things that distinguishes it from other sorting algorithms.