Counting Sort Algorithm

Counting Sort Algorithm

Counting Sort is an integer sorting algorithm that is based on counting the number of occurrences of each distinct element in the input array. The idea is to determine, for each distinct element, the number of elements less than or equal to it. This allows us to place each element directly into its correct position in the sorted output.

Counting Sort is particularly efficient when the range of input values (the difference between the maximum and minimum elements) is not significantly larger than the number of elements to be sorted. It is a non-comparative sorting algorithm, which means that it doesn't rely on comparing the elements directly.

How Counting Sort Works

1. Find the Range of Input: We first find the minimum and maximum elements in the array to determine the range of the data. This helps us decide how large the counting array should be.

2. Create a Counting Array: We create an auxiliary array (often called the counting array) where the index represents the element's value and the value at that index represents the frequency of that element in the input array.

3. Count the Frequency of Elements: Iterate over the input array and for each element, increment the value at its corresponding index in the counting array. For example, if the element is 5, we increment the value at index 5 of the counting array.

4. Cumulative Count: To determine the positions of the elements in the sorted array, we modify the counting array to store the cumulative count. This allows us to place each element at its correct index in the output array.

5. Place Elements in Sorted Order: Finally, we place each element in its correct position in the output array, using the counting array to determine its position.

6. Copy to Original Array: After sorting, we copy the elements from the output array back into the original array if necessary.

Steps of Counting Sort

1. Find the range of the input (minimum and maximum values).
2. Create a counting array where each index corresponds to a value in the input range.
3. Count the frequency of each element in the input array.
4. Modify the counting array to hold the cumulative count.
5. Place elements in the correct position in the output array based on the cumulative counts.
6. Copy the sorted elements back to the original array (optional).

Counting Sort Pseudocode

// Function to perform Counting Sort
void countingSort(int arr[], int n) {
    // Step 1: Find the maximum and minimum elements in the array
    int maxVal = arr[0], minVal = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxVal) maxVal = arr[i];
        if (arr[i] < minVal) minVal = arr[i];
    }

    // Step 2: Create a counting array to store frequencies of each value
    int range = maxVal - minVal + 1;  // range of input values
    int count[range] = {0};            // initialize count array to 0

    // Step 3: Count the occurrences of each element in the input array
    for (int i = 0; i < n; i++) {
        count[arr[i] - minVal]++;
    }

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

    // Step 5: Place the elements in the correct position in the output array
    int output[n];  // output array to store the sorted elements
    for (int i = n - 1; i >= 0; i--) {  // we iterate backwards to maintain stability
        output[count[arr[i] - minVal] - 1] = arr[i];
        count[arr[i] - minVal]--;
    }

    // Step 6: Copy the sorted elements back into the original array
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

Example of Counting Sort

Let’s walk through an example of how Counting Sort works:

Consider the array:

arr = [4, 2, 2, 8, 3, 3, 1]

Step 1: Find the Range

The maximum element is 8 and the minimum element is 1. The range of values is from 1 to 8.

Step 2: Create a Counting Array

We create a counting array of size 8 - 1 + 1 = 8. The counting array represents the frequency of each value in the input array, but since the minimum value is 1, we offset by subtracting 1 from each element when updating the count.

Initially, the count array looks like this:

count = [0, 0, 0, 0, 0, 0, 0, 0]

Step 3: Count the Frequency

We count how many times each number appears in the array:

• 4 appears once
• 2 appears twice
• 8 appears once
• 3 appears twice
• 1 appears once

After counting, the count array becomes:

count = [1, 2, 2, 1, 1, 0, 0, 1]

Step 4: Modify the Count Array to Store Cumulative Count

To determine the positions of elements in the sorted output, we modify the count array to store the cumulative count:

count = [1, 3, 5, 6, 7, 7, 7, 8]

Now, the count array indicates that:

• 1 element is ≤ 1
• 3 elements are ≤ 2
• 5 elements are ≤ 3
• 6 elements are ≤ 4
• 7 elements are ≤ 8

Step 5: Place Elements in Correct Position

Now, we use the count array to place the elements in their correct positions in the output array. We iterate over the input array backwards to maintain the stability of the sort (elements with the same value will remain in their original relative order).

• First, place 1 in the output array at position count[1] - 1 = 0.
• Place 3 at count[3] - 1 = 5.
• Place another 3 at count[3] - 2 = 4.
• Place 2 at count[2] - 1 = 2.
• Place another 2 at count[2] - 2 = 1.
• Place 4 at count[4] - 1 = 6.
• Place 8 at count[8] - 1 = 7.

The output array becomes:

output = [1, 2, 2, 3, 3, 4, 8]

Step 6: Copy the Sorted Elements Back

Finally, copy the elements from the output array back into the original array:

arr = [1, 2, 2, 3, 3, 4, 8]

Time Complexity of Counting Sort

The time complexity of Counting Sort is as follows:

1. Counting the Frequencies: This step takes O(n) time, where n is the number of elements in the input array.

2. Cumulative Count: Modifying the count array to store cumulative counts takes O(k) time, where k is the range of the input (the difference between the maximum and minimum values).

3. Placing Elements in the Output Array: This step also takes O(n) time because we iterate over the input array.

Thus, the overall time complexity of Counting Sort is:

• O(n + k), where n is the number of elements and k is the range of the input values.

Space Complexity of Counting Sort

The space complexity of Counting Sort is:

• O(n + k), where n is the number of elements in the input array and k is the range of input values.

We need an additional count array of size k and an output array of size n to store the sorted elements.

Advantages of Counting Sort

1. Efficient for Small Ranges: Counting Sort is very efficient when the range of input values (k) is small relative to the number of elements (n), as the time complexity is linear in terms of n and k.
2. Stable Sort: Counting Sort is stable, which means that it preserves the relative order of elements with equal keys.
3. Non-Comparative: It doesn’t rely on element comparisons, making it faster than comparison-based algorithms like Quick Sort or Merge Sort for certain datasets.

Disadvantages of Counting Sort

1. Requires a Known Range: Counting Sort works only when the range of input values (k) is known and relatively small. For large ranges, it can become inefficient and consume too much memory.
2. Space Complexity: Counting Sort requires extra space proportional to the range of input values, which can be a drawback if the range is large.
3. Limited to Integer Data: Counting Sort