Sorting is one of the fundamental operations in computer science. Whether you’re dealing with numbers, strings, or more complex data types, sorting can be a critical part of algorithms that power everything from databases to search engines. While there are many sorting algorithms out there, one lesser-known but highly efficient algorithm is Counting Sort.
In this blog, we’ll dive deep into Counting Sort: how it works, when to use it, its time and space complexity, and explore some practical examples of how it can be applied.
What is Counting Sort?
Counting Sort is an integer sorting algorithm that works by counting the occurrences of each distinct element in the array. This count is then used to determine the position of each element in the sorted output.
Unlike comparison-based algorithms like Quick Sort or Merge Sort, which operate by comparing elements to one another, Counting Sort works by using an auxiliary array to “count” how many times each element occurs. By knowing the count of each value, it can then place the elements in their correct position in the sorted array without performing any comparisons.
How Does Counting Sort Work?
Counting Sort works by following these basic steps:
- Find the Range of Input: First, we find the minimum and maximum values in the array to determine the range of numbers we need to count.
- Create a Count Array: Next, we create a counting array (let’s call it
count[]), where the index represents the values in the input array, and the value at each index represents how many times that value appears. - Store Counts: We traverse through the original array and for each element, increment its corresponding index in the
count[]array. - Cumulative Count: Modify the
count[]array by transforming each element to represent the cumulative count of elements up to that index. This means that each position in thecount[]array will tell us how many elements are less than or equal to the current index. - Place Elements in Sorted Order: Now, using the cumulative
count[]array, we can place the elements from the input array into their correct sorted position in the output array. - Copy the Sorted Array: Finally, copy the sorted values back into the original array (or return the sorted array, depending on the implementation).
Example of Counting Sort
Let’s walk through a simple example to better understand how Counting Sort works:
Input Array:
[4, 2, 2, 8, 3, 3, 1, 4]
Step 1: Find the Range of Input
The minimum value is 1, and the maximum value is 8. Therefore, the range of values in the array is from 1 to 8.
Step 2: Create the Count Array
We create an auxiliary count array with a size of 9 (because the values range from 1 to 8, and we’ll use 0-based indexing).
Initially, the count array is empty:
count[] = [0, 0, 0, 0, 0, 0, 0, 0, 0]
Step 3: Store Counts
We now traverse through the original array, and for each element, we increment the corresponding index in the count array.
- For
4, incrementcount[4]→count[4] = 1 - For
2, incrementcount[2]→count[2] = 1 - For
2, incrementcount[2]→count[2] = 2 - For
8, incrementcount[8]→count[8] = 1 - For
3, incrementcount[3]→count[3] = 1 - For
3, incrementcount[3]→count[3] = 2 - For
1, incrementcount[1]→count[1] = 1 - For
4, incrementcount[4]→count[4] = 2
After this step, the count[] array becomes:
count[] = [0, 1, 2, 2, 2, 0, 0, 0, 1]
Step 4: Cumulative Count
We modify the count[] array to represent the cumulative count, which tells us how many elements are less than or equal to each index:
count[1] = count[1] + count[0] = 1count[2] = count[2] + count[1] = 3count[3] = count[3] + count[2] = 5count[4] = count[4] + count[3] = 7count[5] = count[5] + count[4] = 7count[6] = count[6] + count[5] = 7count[7] = count[7] + count[6] = 7count[8] = count[8] + count[7] = 8
Now, the cumulative count array is:
count[] = [0, 1, 3, 5, 7, 7, 7, 7, 8]
Step 5: Place Elements in Sorted Order
We create a result array output[] and place the elements from the input array into their sorted positions using the cumulative count array.
- Place
4at indexcount[4] - 1 = 1, and then decrementcount[4]. - Place
2at indexcount[2] - 1 = 2, and then decrementcount[2]. - Place
2at indexcount[2] - 1 = 1, and then decrementcount[2]. - Place
8at indexcount[8] - 1 = 7, and then decrementcount[8]. - Place
3at indexcount[3] - 1 = 4, and then decrementcount[3]. - Place
3at indexcount[3] - 1 = 3, and then decrementcount[3]. - Place
1at indexcount[1] - 1 = 0, and then decrementcount[1]. - Place
4at indexcount[4] - 1 = 6, and then decrementcount[4].
After this step, the output[] array becomes:
output[] = [1, 2, 2, 3, 3, 4, 4, 8]
Step 6: Copy the Sorted Array
Finally, copy the sorted elements from output[] back to the original array, or return the sorted array:
arr[] = [1, 2, 2, 3, 3, 4, 4, 8]
When to Use Counting Sort
Counting Sort has several advantages, but it’s not suitable for all cases. Let’s go over when it is most effective:
Pros:
- Linear Time Complexity: When the range of input values (the difference between the maximum and minimum values) is not significantly larger than the number of elements to be sorted, Counting Sort can perform in linear time, i.e., O(n + k), where
nis the number of elements in the input array andkis the range of input values. - Non-Comparison Based: Unlike comparison-based algorithms, Counting Sort doesn’t suffer from the O(n log n) lower bound on time complexity. This makes it faster for certain datasets.
- Stable Sort: Counting Sort is a stable sort, meaning it preserves the relative order of elements with equal keys.
Cons:
- Space Complexity: Counting Sort requires extra space proportional to the range of the input values. If the range is large (i.e.,
kis large), the space complexity becomes a significant issue. - Limited to Integer Data: Counting Sort only works efficiently with non-negative integers (or can be adapted to work with other data types with some modifications).
When to Use:
- When sorting integers or categorical data with a small range.
- In scenarios where space isn’t a major concern and the range of values is known to be small (e.g., sorting grades in a class, sorting pixel colors in images).
Time and Space Complexity
- Time Complexity: O(n + k), where:
nis the number of elements in the input array.kis the range of the input values (the difference between the maximum and minimum values).- Space Complexity: O(k), because we use an auxiliary array to store the counts.
For large k, Counting Sort can become inefficient compared to other algorithms like Quick Sort or Merge Sort.
Counting Sort is an efficient and unique sorting algorithm that works well under specific conditions. Its ability to sort in linear time makes it a powerful tool for sorting integer-based or categorical data with a small range. However, the algorithm’s limitations in terms of space and data type make it unsuitable for every use case. When applied in the right contexts, Counting Sort can outperform comparison-based algorithms, especially when the range of data is limited and space usage is not a major concern.
FAQs on Counting Sort
1. What is Counting Sort?
Counting Sort is a non-comparison-based sorting algorithm that counts the occurrences of each element in the input array. It then uses this count to place the elements in their correct position in the sorted output.
2. What types of data can Counting Sort handle?
Counting Sort works primarily with integers or categorical data. It is not suitable for sorting floating-point numbers or strings unless they are converted to a suitable integer representation.
3. When is Counting Sort most efficient?
Counting Sort is most efficient when the range of input values (k) is small relative to the number of elements (n). If k is large, its performance can degrade due to high space complexity.
4. What is the time complexity of Counting Sort?
The time complexity of Counting Sort is O(n + k), where n is the number of elements and k is the range of input values. This makes it linear when k is small relative to n.
5. What is the space complexity of Counting Sort?
The space complexity is O(k), where k is the range of the input values. The algorithm requires an auxiliary array to count occurrences of each element.
6. Is Counting Sort a stable sorting algorithm?
Yes, Counting Sort is a stable algorithm, meaning that it preserves the relative order of elements with equal keys.
7. Can Counting Sort be used for floating-point numbers?
Counting Sort is not designed to handle floating-point numbers directly. However, it can be adapted to work with them by converting the values to integers (e.g., scaling decimals into whole numbers).
8. What are the advantages of Counting Sort?
- Linear time complexity when the range of values (
k) is small. - Stable sorting.
- Efficient for sorting integers and categorical data.
9. What are the disadvantages of Counting Sort?
- It requires extra space proportional to the range of input values, which can be inefficient for large ranges.
- It only works with non-negative integers or data that can be mapped to integers.
10. Can Counting Sort be used for negative numbers?
By default, Counting Sort is not designed to handle negative numbers. However, you can adjust the algorithm by shifting all numbers so that the smallest number becomes zero, effectively transforming the problem into one involving non-negative integers.
11. How does Counting Sort compare to other sorting algorithms?
Unlike comparison-based sorting algorithms like Quick Sort or Merge Sort (which have a lower bound of O(n log n) time complexity), Counting Sort can achieve linear time complexity O(n + k) when the range of the numbers is small. However, it’s limited by space complexity and works best when the data has a small range.
12. Can Counting Sort be used in real-world applications?
Yes, Counting Sort is used in situations where data falls within a known, limited range. It is often applied in applications like sorting grades, counting occurrences in histograms, or even in specific image processing tasks like sorting pixel colors.
Read More –
The 6 Most Efficient Methods for Finding the Minimum Element in a Rotated Sorted Array – https://kamleshsingad.com/wp-admin/post.php?post=5440&action=edit
A Deep Dive into Counting Sort: 7 Critical Factors for Success – https://kamleshsingad.com/wp-admin/post.php?post=5435&action=edit
How to Work with Virtual Environments in Python – https://kamleshsingad.com/wp-admin/post.php?post=5348&action=edit
