Counting Sort in Data Structures

Amit Kumar Ghosh 14 min read

15 Jun 2023

Intermediate

277 Views

Introduction

Have you ever wanted an efficient way to sort big datasets? Counting sort might be the key. One of the popular sorting algorithms used in data structures, Counting Sort is easy to understand and can save time by sorting large amounts of data quickly. In this article, we'll talk about what counting sort is, how it works, its advantages and disadvantages, and when you should use it for your project. So don't miss out on learning all about this powerful technique today!

What is Counting Sort in Data Structure?

Counting sort is a linear sorting algorithm that works great for a specific range of values. Instead of comparing elements, it counts the number of occurrences of each element and uses that information to determine the sorted order. This makes counting sort a highly efficient algorithm for sorting integers, with a time complexity of O(n+k), where k is the range of values. Since counting sort does not need any comparison to sort the elements, it can easily outperform other sorting algorithms, such as quicksort or mergesort, in terms of speed. Overall, counting sort is a powerful tool in data structures that makes sorting integers a breeze.

Working of Counting Sort

Here's a step-by-step explanation of how counting sort works:
Determine the range: Find the minimum and maximum values in the input array. This step helps determine the range of values that need to be sorted.
Counting frequencies: Create a "count" array with a size equal to the range of values plus one. Initialize all the elements in the count array to 0. The count array will be used to store the frequencies of each unique element in the input array.
Count the occurrences: Traverse the input array, and for each element, increment the corresponding count array index by 1. The count array will now contain the number of occurrences of each element in the input array.
Calculate cumulative counts: Modify the count array by calculating the cumulative sum of the frequencies. Each count value represents the number of elements that are less than or equal to the corresponding index.
Position the elements: Create an output array with the same size as the input array. Iterate through the input array from right to left. For each element, use the count array to determine its correct position in the output array. Decrement the count value for the corresponding element in the count array.

Copy the elements: After positioning each element in the output array, the output array will contain the sorted elements

Counting Sort Algorithm

countingSort(array, size)
   max <- find largest element in array
   initialize count array with all zeros
   for j <- 0 to size
     find the total count of each unique element and 
     store the count at jth index in the count array
   for i <- 1 to max
     find the cumulative sum and store it in count array itself
   for j <- size down to 1
     restore the elements to array
     decrease count of each element restored by 1

Implementation of Counting Sort


 # Counting sort in Python programming


 def countingSort(array):
     size = len(array)
     output = [0] * size
 
     # Initialize count array
     count = [0] * 10
 
     # Store the count of each elements in count array
     for i in range(0, size):
         count[array[i]] += 1
 
     # Store the cummulative count
     for i in range(1, 10):
         count[i] += count[i - 1]
 
     # Find the index of each element of the original array in count array
     # place the elements in output array
     i = size - 1
     while i >= 0:
         output[count[array[i]] - 1] = array[i]
         count[array[i]] -= 1
         i -= 1
 
     # Copy the sorted elements into original array
     for i in range(0, size):
         array[i] = output[i]
 
 
 data = [ 5, 4, 4, 6, 3, 3, 2 ]
 countingSort(data)
 print("Sorted Array in Ascending Order: ")
 print(data)

Output:

 The output of the code will be:
2, 3, 3, 4, 4, 5, 6

Counting Sort Complexity

The time complexity of Counting Sort is O(n+k), where n is the number of elements to be sorted, and k is the input range. In other words, the algorithm's runtime is proportional to the sum of the size of the input and the range of values in the input array. Counting Sort is a linear-time sorting algorithm, meaning that its time, counting sort complexity grows linearly with the size of the input. This makes it faster than comparison-based sorting algorithms like Merge Sort and Quick Sort, which have a worst-case time complexity of O(n log n). However, Counting Sort requires additional space proportional to the range of the input array, which makes it less efficient in terms of memory usage than other sorting algorithms like Insertion Sort and Selection Sort. Counting Sort is an efficient algorithm for sorting integers within a small range and can be used as a subroutine in more complex sorting algorithms.

Visual Illustration of Counting Sort Algorithm

Counting Sort is a non-comparative sorting algorithm that works by determining the number of elements in a given range and using that information to place the elements in their correct sorted positions. It is particularly efficient when the range of input values is small compared to the number of elements to be sorted.

Let's suppose we have an array of integers to sort: [4, 2, 6, 3, 2, 1, 7, 4]. To visualize the Counting Sort algorithm step-by-step, we'll use a graphical representation. I'll use brackets to represent the elements and their frequencies.

Initialization:
- Create a count array to store the frequency of each element.
- In this case, the count array will have the length of the maximum element in the input array plus one, so it would be [0, 0, 0, 0, 0, 0, 0, 0].
- Draw the count array:

Counting Frequencies:

Traverse the input array and increment the count for each element in the count array.

As we encounter an element, we increment the corresponding count.

After traversing the input array, the count array will be updated as follows:

Cumulative Sum:

Modify the count array by taking the cumulative sum of its elements.

Each element will store the sum of all previous elements.

After the cumulative sum, the count array will be updated as follows:

Placing Elements:

Create a temporary output array of the same length as the input array.
Starting from the end of the input array, iterate over each element.
Find the position of the element in the count array and place it in the temporary output array.
Decrement the count of that element in the count array.
Repeat this process for all elements in the input array.

After placing all the elements, the temporary output array will be:

Finalizing:

The temporary output array contains the sorted elements.
Copy the sorted elements back to the original input array.
The sorted input array will be:

This visual representation demonstrates how Counting Sort works step by step. It utilizes frequency counting and cumulative sum to determine the correct position of each element, resulting in a sorted array.

Counting Sort Applications

One of the main applications of counting sort is when the input sequence contains a relatively small range of integer values. For example, if we have an array of integers ranging from 1 to 1000, and we want to sort it, counting sort can be a good choice. Here's how counting sort can be used in this scenario:

Find the maximum value in the array. In this case, it's 1000.
Create an array C of size 1001 (one more than the maximum value). Initialize all the elements of C to 0.
Iterate through the input array and, for each element x, increment the corresponding element in C by 1. For example, if the input array contains the element 500, then we would increment the value of C[500] by 1.
Compute the prefix sum of C. This means that we add each element of C to the previous element, starting from the first element. At the end of this step, C[i] contains the number of elements in the input array that are less than or equal to i.
Create an output array B of the same size as the input array.
Iterate through the input array backward, and for each element x, place it in the output array at the position indicated by C[x]. Decrement the value of C[x] by 1.
The output array B now contains the sorted sequence.

Advantages of Counting Sort

Linear time complexity: Counting Sort has a linear time complexity of O(n+k), where n is the number of elements to be sorted and k is the range of input values. This makes it one of the fastest sorting algorithms when compared to comparison-based sorting algorithms like QuickSort or MergeSort, which have an average time complexity of O(n log n).
No comparison operations: Counting Sort does not rely on comparison operations between elements, unlike many other sorting algorithms. Instead, it counts the occurrences of each distinct element and determines their positions in the sorted output directly. This absence of comparisons makes it particularly useful when the elements being sorted are non-comparable or when the comparison operation is costly.
Suitable for small range of input values: Counting Sort performs exceptionally well when the range of input values (k) is relatively small compared to the number of elements (n). It creates a counting array of size k to keep track of the occurrences of each distinct element. The small range of values allows Counting Sort to achieve its linear time complexity.
Stable sorting: Counting Sort is a stable sorting algorithm, meaning that it maintains the relative order of elements with equal values. This property is particularly useful when sorting objects that have multiple keys or when preserving the original order of equal elements is necessary.
Efficient for integer sorting: Counting Sort is especially efficient for sorting integer values. It can handle negative numbers as well by appropriately adjusting the counting array and output array.
Simple implementation: Counting Sort has a relatively simple implementation compared to some other sorting algorithms. It involves counting the occurrences of elements, calculating cumulative counts, and placing elements in their correct positions in the output array. Its simplicity makes it easier to understand, implement, and debug.

Disadvantages of Counting Sort

Limited Applicability: The counting sort is only applicable when the range of input values is small and known beforehand. It relies on creating a count array with a size equal to the maximum element in the input array, which can be memory-intensive or even impractical for large ranges of values.
Memory Requirement: The counting sort requires additional memory to store the count array, which can be a disadvantage when working with large input arrays or limited memory resources. The memory usage is proportional to the range of input values, not the number of elements being sorted.
Not In-place: Counting sort is not an in-place sorting algorithm. It needs extra space to create the count array and an output array to store the sorted elements. This means that the algorithm requires additional memory proportional to the size of the input array.
Not Stable for Arbitrary Data: The counting sort is not a stable sorting algorithm by default. Stability refers to the preservation of the relative order of equal elements. If there are multiple occurrences of the same element, the order in the output may not be the same as the order in the input.
Limited to Integer Values: The counting sort is designed for sorting integer values. It cannot be directly applied to sort objects or floating-point numbers. Any conversion or mapping of non-integer data types to integers is required before using counting sort, which can be cumbersome and time-consuming.
Time Complexity: Although the counting sort has a linear time complexity of O(n + k), where n is the number of elements and k is the range of values, it is not always the most efficient sorting algorithm. Other comparison-based sorting algorithms like quicksort or mergesort can have better average-case time complexity for larger datasets, even though they have a worst-case time complexity of O(nlogn).

Summary

In conclusion, Counting Sort is an extremely useful and efficient sorting algorithm that can be applied to many scenarios. Its time complexity makes it a great choice for large datasets and its stability ensures that duplicate items remain in the same order in which they appear. While not all sorting algorithms can adjust easily to changing data lengths, Counting Sort is able to adapt quickly to a number of contexts due to its features. With an overall understanding of the purpose and advantages of this counting methodology, implementers can better utilize Counting Sort for their data arrays. If you're looking for an efficient way to sort your data arrays then remember to consider Counting Sort and put some counting power behind that next big project!