Skip to main content

Sorting

Counting Sort

Counting Sort is a simple sorting algorithm that sorts an array by counting the occurrences of each unique element and using those counts to determine their correct positions. It is efficient for datasets with a limited range of values and does not rely on comparisons to sort.

Since the name itself indicates that we need to count the elements, let's directly jump into the steps involved in this algorithm.

Steps Involve in the Algorithm

  1. Find the Maximum Value:
    • Let max_val be the largest element in arr.
  • Initialize Count Array:
    • Create a count array count of size max_val + 1 (since array indices start from 0).
    • Initialize all elements of count to 0.
  • Count Occurrences:
    • For each element x in arr, increment count[x] (since x is directly used as the index).
  • Modify Count Array (Cumulative Count):
    • For each index i from 1 to max_val:
      • Update count[i] = count[i] + count[i - 1].
  • Build the Output Array:
    • Create an output array output of the same size as arr.
    • Traverse arr in reverse order (to maintain stability):
      • Place each element at the position count[x] - 1 in output.
      • Decrement count[x].
  • Copy Back to Original Array (Optional):
    • Copy the elements of output back into arr.

Let us understand it through animations

0:00
/3:42

Let us understand a step-by-step working of Counting Sort with an example : 

Suppose we have the following array of integers nums: [4, 2, 2, 8, 3, 3, 1] that we want to sort in ascending order:

Step by Step working

Initial array: arr=[4, 2, 2, 8, 3, 3, 1]

Step 1: Find the Maximum Value

  • First, we find the maximum value in the array: max_val=8

This tells us the size of our count array, which will have 9 elements (since the maximum value is 8).

Step 2: Initialize the Count Array

  • We create a count array with size max_val + 1 (i.e., 9), and initialize all elements to 0: count=[0,0,0,0,0,0,0,0,0]

Step 3: Count Occurrences

  • We iterate through the input array, and for each element x, we increment count[x]. The value of x is used directly as the index.
    • For x = 4, increment count[4]: count=[0,0,0,0,1,0,0,0,0]
    • For x = 2, increment count[2]: count=[0,0,1,0,1,0,0,0,0]
    • For x = 2, increment count[2] again :count=[0,0,2,0,1,0,0,0,0]
    • For x = 8, increment count[8]: count=[0,0,2,0,1,0,0,0,1]
    • For x = 3, increment count[3]: count=[0,0,2,1,1,0,0,0,1]
    • For x = 3, increment count[3] again :count=[0,0,2,2,1,0,0,0,1]
    • For x = 1, increment count[1]: count=[0,1,2,2,1,0,0,0,1]

Step 4: Modify Count Array (Cumulative Count)

  • Convert the count array to a cumulative count array:
    • For i = 1 : count[1]=count[0]+count[1]=0+1=1
    • For i = 2 : count[2]=count[1]+count[2]=1+2=3
    • For i = 3 : count[3]=count[2]+count[3]=3+2=5
    • For i = 4 : count[4]=count[3]+count[4]=5+1=6
    • For i = 5 : count[5]=count[4]+count[5]=6+0=6
    • For i = 6 : count[6]=count[5]+count[6]=6+0=6
    • For i = 7 : count[7]=count[6]+count[7]=6+0=6
    • For i = 8 : count[8]=count[7]+count[8]=6+1=7
  • After this step: count=[0,1,3,5,6,6,6,6,7]

Step 5: Build the Output Array

  • Create an empty output array of the same size as the input array:output=[0,0,0,0,0,0,0]
  • Traverse the input array in reverse order to maintain stability:
    • For x = 1: Place 1 in output[count[1] - 1] = output[0], then decrement count[1]: output=[1,0,0,0,0,0,0]
    • For x = 3: Place 3 in output[count[3] - 1] = output[4], then decrement count[3]: output=[1,0,0,0,3,0,0]
    • For x = 3: Place 3 in output[count[3] - 1] = output[3], then decrement count[3]: output=[1,0,0,3,3,0,0]
    • For x = 8: Place 8 in output[count[8] - 1] = output[6], then decrement count[8]: output=[1,0,0,3,3,0,8]
    • For x = 2: Place 2 in output[count[2] - 1] = output[2], then decrement count[2]: output=[1,0,2,3,3,0,8]
    • For x = 2: Place 2 in output[count[2] - 1] = output[1], then decrement count[2]: output=[1,2,2,3,3,0,8]
    • For x = 4: Place 4 in output[count[4] - 1] = output[5], then decrement count[4]:output=[1,2,2,3,3,4,8]

Step 6: Copy Back to the Original Array

  • Finally, copy the output array back to the original array arr if needed arr=[1,2,2,3,3,4,8]

Final Sorted Array: arr=[1,2,2,3,3,4,8]

Code Implementation
C++ 
class Solution {
public:
    // Function to perform Counting Sort
    void countingSort(vector<int>& arr) {
        // Step 1: Find the maximum value in the array to define the size of the count array
        int max_val = *max_element(arr.begin(), arr.end());

        // Step 2: Initialize the count array of size max_val + 1, all elements set to 0
        vector<int> count(max_val + 1, 0);

        // Step 3: Count the occurrences of each element in the arr array
        for (int num : arr) {
            count[num]++;  // Increment the count of the corresponding element
        }

        // Step 4: Modify the count array to store cumulative counts (prefix sum)
        for (int i = 1; i <= max_val; i++) {
            count[i] += count[i - 1];  // Add the count of the previous element to the current count
        }

        // Create the output array to store the sorted values
        vector<int> output(arr.size());

        // Step 5: Build the output array by placing elements at the correct positions
        // We traverse the original array in reverse order to maintain stability
        for (int i = arr.size() - 1; i >= 0; i--) {
            int num = arr[i];
            output[count[num] - 1] = num;  // Place the element at the correct index in output
            count[num]--;  // Decrease the count for the current element
        }

        // Step 6: Copy the sorted elements from the output array back to the original array
        for (int i = 0; i < arr.size(); i++) {
            arr[i] = output[i];  // Copy the sorted values back to the arr array
        }
    }
};

Java 
class Solution {
    // Function to perform Counting Sort
    public void countingSort(int[] arr) {
        // Step 1: Find the maximum value in the array to define the size of the count array
        int max_val = Arrays.stream(arr).max().getAsInt();

        // Step 2: Initialize the count array of size max_val + 1, all elements set to 0
        int[] count = new int[max_val + 1];

        // Step 3: Count the occurrences of each element in the arr array
        for (int num : arr) {
            count[num]++;
        }

        // Step 4: Modify the count array to store cumulative counts (prefix sum)
        for (int i = 1; i <= max_val; i++) {
            count[i] += count[i - 1];
        }

        // Create the output array to store the sorted values
        int[] output = new int[arr.length];

        // Step 5: Build the output array by placing elements at the correct positions
        for (int i = arr.length - 1; i >= 0; i--) {
            int num = arr[i];
            output[count[num] - 1] = num;  // Place the element at the correct index in output
            count[num]--;  // Decrease the count for the current element
        }

        // Step 6: Copy the sorted elements from the output array back to the original array
        System.arraycopy(output, 0, arr, 0, arr.length);
    }
}

Python 
class Solution:
    # Function to perform Counting Sort
    def countingSort(self, arr):
        # Step 1: Find the maximum value in the array to define the size of the count array
        max_val = max(arr)

        # Step 2: Initialize the count array of size max_val + 1, all elements set to 0
        count = [0] * (max_val + 1)

        # Step 3: Count the occurrences of each element in the arr array
        for num in arr:
            count[num] += 1

        # Step 4: Modify the count array to store cumulative counts (prefix sum)
        for i in range(1, len(count)):
            count[i] += count[i - 1]

        # Create the output array to store the sorted values
        output = [0] * len(arr)

        # Step 5: Build the output array by placing elements at the correct positions
        for i in range(len(arr) - 1, -1, -1):  # Traverse arr in reverse order for stability
            num = arr[i]
            output[count[num] - 1] = num  # Place the element at the correct index in output
            count[num] -= 1  # Decrease the count for the current element

        # Step 6: Copy the sorted elements from the output array back to the original array
        for i in range(len(arr)):
            arr[i] = output[i]  # Copy the sorted values back to arr

Javascript 
// Class for implementing Counting Sort
class Solution {
    // Function to perform Counting Sort
    countingSort(arr) {
        // Step 1: Find the maximum value in the array to define the size of the count array
        let max_val = Math.max(...arr);

        // Step 2: Initialize the count array of size max_val + 1, all elements set to 0
        let count = new Array(max_val + 1).fill(0);

        // Step 3: Count the occurrences of each element in the arr array
        for (let num of arr) {
            count[num]++;
        }

        // Step 4: Modify the count array to store cumulative counts (prefix sum)
        for (let i = 1; i <= max_val; i++) {
            count[i] += count[i - 1];
        }

        // Create the output array to store the sorted values
        let output = new Array(arr.length);

        // Step 5: Build the output array by placing elements at the correct positions
        for (let i = arr.length - 1; i >= 0; i--) {
            let num = arr[i];
            output[count[num] - 1] = num;  // Place the element at the correct index in output
            count[num]--;  // Decrease the count for the current element
        }

        // Step 6: Copy the sorted elements from the output array back to the original array
        for (let i = 0; i < arr.length; i++) {
            arr[i] = output[i];  // Copy the sorted values back to arr
        }
    }
}

Time Complexity : O(n+k)

  1. Finding the maximum value (max_val) in the array: We need to traverse the entire array once to find the maximum value, So time complexity: O(n), where n is the number of elements in the array.
  2. Counting occurrences of each element: In this step, we traverse the array once, and for each element, we increment its count in the count array. So time complexity: O(n), where n is the number of elements in the array.
  3. Calculating the cumulative count: After counting the occurrences, we need to traverse the count array to calculate the cumulative counts (prefix sum). This array has a size of max_val + 1. So time complexity: O(k), where k is the range of the input (i.e., the maximum value max_val).
  4. Placing elements in the sorted order: We traverse the input array once again to place each element in its correct position in the output array. This step also requires us to use the count array to determine the position for each element. So time complexity: O(n), where n is the number of elements in the array.
  5. Copying elements back to the original array: Finally, we copy the sorted elements from the output array back to the original arr array. Time complexity: O(n), where n is the number of elements in the array.

Total Time Complexity: The overall time complexity of Counting Sort is dominated by the two major operations:

  • Finding the maximum value: O(n)
  • Counting occurrences and placing elements in the correct order: O(n)
  • Cumulative count calculation: O(k), where k is the range of the elements.

Thus, the total time complexity is: O(n+k), where n is the number of elements in the array and k is the range of input values (i.e., the maximum value of the elements).

Space Complexity : O(n+k)

  1. Count array: The count array is of size max_val + 1, where max_val is the maximum element in the input array. Therefore, the space complexity for the count array is O(k), where k is the range of the input elements.
  2. Output array: We need an output array of the same size as the input array, which takes O(n) space.
  3. Auxiliary space: The space used by the input array and output array is not counted towards auxiliary space since they are input and output. The only additional space used for sorting is the count array and the output array.

Total Space Complexity: The space complexity is dominated by the count array and the output array. Hence, the total space complexity is: O(n+k).

where: n is the number of elements in the array, k is the range of the input values (i.e., the maximum value of the elements).

Stability of Algorithm

Counting Sort is a stable sorting algorithm, meaning it preserves the relative order of equal elements in the sorted array.

This is achieved by iterating through the input array from right to left when placing elements into the output array. By doing this, if two elements have the same value, the one that appears later in the original array will be placed first in the sorted array, preserving their original order.

Application of Counting Sort

  1. Sorting small ranges of integers: Counting Sort is efficient when the range of input values k is small compared to the number of elements n. For example, sorting integers between 0 and 1000 with a large dataset.
  2. Sorting fixed-size data: It works well for sorting fixed-size integers, such as sorting grades (0-100) or small datasets with limited value ranges.
  3. Efficient in specific scenarios:
    • Image Processing: For tasks like sorting pixel values (in grayscale images), where values are limited (e.g., 0 to 255).
    • Radix Sort: Counting Sort is used as a subroutine in Radix Sort, especially when sorting by individual digits or character positions.
  5. Distribution of objects in a certain range: It's useful in applications that involve distributing items into buckets (e.g., binning or bucketing data in range-specific bins).
  6. Computational biology and genomics: Used for counting and sorting nucleotide sequences or similar data types with restricted value ranges.
  7. Counting frequencies: Frequently used for calculating the frequency of elements in a dataset, like word count analysis or histogram creation.
💡
Showcase your skills by joining LearnYard Technologies FZ-LLC as a Technical Content Writer. Apply now and inspire the next generation of learners—fill out the form: https://forms.gle/CGDsbGkcapSfvXKM8