Counting sort

Counting Sort

Counting sort is an efficient sorting algorithm that operates on a set of integers within a specific range. It works by counting the number of occurrences of each distinct element in the input array and then using this information to determine the correct position of each element in the sorted output array.

Algorithm

The counting sort algorithm can be summarized in the following steps:

1. Find the maximum element in the input array and determine the range of elements (from 0 to the maximum value).

2. Create a count array of size equal to the range, initialized with all zeros.

3. Iterate through the input array and increment the count of each element in the count array.

4. Modify the count array by adding the previous count to the current count. This step helps in determining the correct position of each element in the sorted output array.

5. Create a temporary output array of the same size as the input array.

6. Iterate through the input array in reverse order. For each element, find its correct position in the output array using the count array, decrement the count of that element, and place it in the output array.

7. Copy the elements from the output array back to the input array, resulting in a sorted array.

Example

Let's consider an example to understand the counting sort algorithm better. Suppose we have an input array [4, 2, 2, 8, 3, 3, 1]. The maximum element in this array is 8, so the range of elements is from 0 to 8.

1. Create a count array of size 9 (range + 1) and initialize it with zeros: [0, 0, 0, 0, 0, 0, 0, 0, 0].

2. Iterate through the input array and increment the count of each element in the count array: [1, 2, 2, 1, 0, 0, 0, 1, 0].

3. Modify the count array by adding the previous count to the current count: [1, 3, 5, 6, 6, 6, 6, 7, 7].

4. Create a temporary output array of the same size as the input array: [0, 0, 0, 0, 0, 0, 0, 0, 0].

5. Iterate through the input array in reverse order. For each element, find its correct position in the output array using the count array, decrement the count of that element, and place it in the output array: [0, 0, 1, 1, 2, 2, 3, 3, 4].

6. Copy the elements from the output array back to the input array: [0, 0, 1, 1, 2, 2, 3, 3, 4].

The input array is now sorted in ascending order using the counting sort algorithm.

Complexity Analysis

The counting sort algorithm has a time complexity of O(n + k), where n is the number of elements in the input array and k is the range of elements. It is considered a linear time sorting algorithm.

However, counting sort requires additional space for the count array and the output array, making its space complexity O(n + k).

Applications

Counting sort is particularly useful when the range of input elements is small compared to the number of elements to be sorted. It is often used as a subroutine in other sorting algorithms, such as radix sort.

See Also

• Sorting algorithm
• Radix sort
• Bucket sort

References

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

2. GeeksforGeeks. (2021). Counting Sort. Retrieved from [1](https://www.geeksforgeeks.org/counting-sort/)