What is Counting Sort Algorithm?

Last updated on December 16th, 2024 at 03:51 am

This article explores the Counting Sort Algorithm, its pseudocode, time complexity, and implementation in popular programming languages like Python and C++.

1. What is Counting Sort Algorithm?

Counting Sort Algorithm is an integer sorting algorithm that works by counting the occurrences of each unique element in the input array. It then calculates the position of each element in the sorted array. It is efficient for sorting integers within a small range.

1. Counting Sort is efficient if the range of input data is not significantly greater than the number of objects to be sorted.
2. It is not a comparison-based sorting. Its running time complexity is O(n) with space proportional to the range of data.
3. This can be used as a subroutine to some other algorithm. It is often used as a subroutine to another sorting algorithm, such as radix sort.
4. It uses partial hashing to count the occurrence of the data object in O(1).
5. It can be extended to work for negative inputs also.

2. How the Counting Sort Algorithm Works

The Counting Sort Algorithm operates by counting the occurrences of each unique element in the input data. It then uses this information to determine the position of each element in the sorted output. Here’s a step-by-step breakdown:

1. Determine the Range: Identify the range of the input data, i.e., the minimum and maximum values.
2. Initialize the Count Array: Create an array of zeroes with a length equal to the range of the input data.
3. Count Occurrences: Traverse the input data and increment the corresponding index in the count array for each element.
4. Accumulate Counts: Modify the count array by adding the count of the previous element to each element. This step helps in determining the position of each element in the sorted array.
5. Build the Output Array: Traverse the input data again, placing each element in its correct position in the output array based on the accumulated counts.
6. Copy to Original Array: If needed, copy the sorted elements back to the original array.

3. Counting Sort Pseudocode

function countingSort(array, maxVal)
    countArray = array of zeros with length maxVal + 1
    outputArray = array of zeros with length of array

    for each number in array
        countArray[number] += 1

    for i from 1 to maxVal
        countArray[i] += countArray[i - 1]

    for each number in array (in reverse)
        outputArray[countArray[number] - 1] = number
        countArray[number] -= 1

    return outputArray

4. Counting Sort Algorithm C++ Implementation:

#include <iostream>
#include <vector>

std::vector<int> counting_sort(std::vector<int>& arr) {
  int max_val = *std::max_element(arr.begin(), arr.end());
  std::vector<int> count(max_val + 1, 0);
  
  for (int num : arr) {
    count[num]++;
  }
  
  std::vector<int> output;
  for (int i = 0; i <= max_val; i++) {
    while (count[i] > 0) {
      output.push_back(i);
      count[i]--;
    }
  }
  
  return output;
}

// Example usage:
int main() {
  std::vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
  std::vector<int> sorted_arr = counting_sort(arr);
  for (int num : sorted_arr) {
    std::cout << num << " ";
  }
  return 0;
}

5. Counting Sort Python Implementation

Here’s an example implementation of the Counting Sort Algorithm in Python:

def counting_sort(arr):
  max_val = max(arr)
  count = [0] * (max_val + 1)
  
  for num in arr:
    count[num] += 1
  
  output = []
  for i in range(max_val + 1):
    while count[i] > 0:
      output.append(i)
      count[i] -= 1
  
  return output

# Example
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print(sorted_arr)  # Output: [1, 2, 2, 3, 3, 4, 8]

6. Advantages of Counting Sort

1. Linear Time Complexity: Counting Sort has a time complexity of O(n + k), where n is the number of elements and k is the range of input.
2. Stable Sort: Counting Sort preserves the relative order of equal elements.
3. Efficient for Small Range: It is very efficient when the range of input elements (k) is not significantly larger than the number of elements (n).

7. Disadvantages of Counting Sort

1. Limited Range: Counting Sort is not suitable for large ranges of numbers or non-integer data.
2. Space Complexity: The algorithm requires additional space for the count array, making it less space-efficient for large ranges.
3. Not Comparison-Based: Counting Sort cannot be used as a general-purpose sorting algorithm since it relies on the numerical range of the data.

8. Counting Sort Time Complexity and Space Complexity

9. Applications of Counting Sort Algorithm

Counting Sort is used when:

• there are smaller integers with multiple counts.
• linear complexity is the need.

FAQs