How To Do Counting Sort in JavaScript

Counting Sort is an efficient, non-comparative sorting algorithm that counts the occurrences of each unique element in the input array. It then uses this count information to place elements in their correct positions in the output array. Unlike comparison-based algorithms such as Quick Sort and Merge Sort, Counting Sort is most effective when dealing with integer values and a known range of data.

This post will cover how Counting Sort works, its JavaScript implementation, and a step-by-step algorithm explanation. We’ll also discuss its time and space complexities and where you might want to use it.

What is Counting Sort?

Counting Sort works by counting the number of occurrences of each distinct element in the input array and using this count to determine the position of each element in the output array. It is particularly effective when the range of the input values is not too large, and the elements are integers.

Counting Sort is stable, meaning it preserves the relative order of elements with equal values.

Pseudocode for Counting Sort

Here’s the pseudocode for Counting Sort:

procedure countingSort(arr, maxValue)
    # Step 1: Create the count array
    count = new array of size maxValue + 1, initialized to 0

    # Step 2: Count the occurrences of each element
    for i = 0 to length(arr) - 1 do
        count[arr[i]] = count[arr[i]] + 1

    # Step 3: Modify the count array to store cumulative counts
    for i = 1 to maxValue do
        count[i] = count[i] + count[i - 1]

    # Step 4: Create the output array and place elements at correct positions
    output = new array of size length(arr)
    for i = length(arr) - 1 down to 0 do
        output[count[arr[i]] - 1] = arr[i]
        count[arr[i]] = count[arr[i]] - 1

    # Step 5: Copy the sorted output array back to the original array
    for i = 0 to length(arr) - 1 do
        arr[i] = output[i]

Time Complexity of Counting Sort

• Best Case: O(n + k) – where n is the number of elements in the array and k is the range of the input data (maxValue). The time complexity depends linearly on both the number of elements and the range of the input.
• Average Case: O(n + k) – Similar to the best case.
• Worst Case: O(n + k) – The worst-case time complexity is still linear, making Counting Sort efficient for small ranges of integers.

Space Complexity of Counting Sort

• Space Complexity: O(n + k) – Counting Sort requires additional space for the count array (size k + 1) and the output array (size n).

JavaScript Implementation of Counting Sort

Let’s implement Counting Sort in JavaScript based on the pseudocode.

// Counting Sort implementation in JavaScript
function countingSort(arr, maxValue) {
    // Step 1: Create and initialize the count array
    let count = new Array(maxValue + 1).fill(0);

    // Step 2: Count the occurrences of each element
    for (let i = 0; i < arr.length; i++) {
        count[arr[i]]++;
    }

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

    // Step 4: Create the output array and place elements in the correct positions
    let output = new Array(arr.length);
    for (let i = arr.length - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

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

    return arr;
}

// Example usage
const arr = [4, 2, 2, 8, 3, 3, 1];
const maxValue = Math.max(...arr);

console.log("Original array:", arr);
console.log("Sorted array:", countingSort(arr, maxValue));

Step-by-Step Explanation of the Code

1. Create the Count Array:
   • We first create a count array of size maxValue + 1, where maxValue is the largest value in the input array. This array will store the number of occurrences of each element in the input array.
   • The array is initialized with zeroes using .fill(0).
2. Count the Occurrences of Each Element:
   • We iterate through the input array and, for each element, increment the corresponding index in the count array. For example, if the element is 4, we increment count[4] by 1.
3. Modify the Count Array:
   • Next, we modify the count array so that each element at index i contains the cumulative count of elements up to index i. This will give us the correct positions of each element in the sorted array.
4. Place Elements in the Output Array:
   • We create an output array and iterate over the input array in reverse order to maintain the stability of the sorting. For each element, we place it in its correct position in the output array based on the cumulative counts stored in the count array.
5. Copy the Output Array Back:
   • Finally, we copy the sorted output array back into the original array, completing the sorting process.

Step-by-Step Walkthrough of Counting Sort with Array

Let’s walk through Counting Sort using the array [4, 2, 2, 8, 3, 3, 1].

Step 1: Create the Count Array

• The largest element in the array is 8, so the count array will have 9 slots (from 0 to 8).
• Initially, the count array is: [0, 0, 0, 0, 0, 0, 0, 0, 0].

---

Step 2: Count the Occurrences of Each Element

• For each element in the array, increment the corresponding index in the count array:
  • After processing the array, the count array becomes: [0, 1, 2, 2, 1, 0, 0, 0, 1].
  • This means there is one occurrence of 1, two occurrences of 2, two occurrences of 3, one occurrence of 4, and one occurrence of 8.

---

Step 3: Modify the Count Array

• Convert the count array into a cumulative count array:
  • The modified count array is: [0, 1, 3, 5, 6, 6, 6, 6, 7].
  • This array now tells us the position of each element in the sorted array.

---

Step 4: Place Elements in the Output Array

• Iterate through the input array in reverse and place each element in its correct position in the output array:
  • The output array after this step: [1, 2, 2, 3, 3, 4, 8].

---

Step 5: Copy the Output Array Back

• Copy the sorted output array back into the original array:
  • The sorted array is now [1, 2, 2, 3, 3, 4, 8].

Pros and Cons of Using Counting Sort

Pros:

1. Linear Time Complexity: Counting Sort runs in linear time for arrays with a known and small range of integer values, making it highly efficient compared to comparison-based algorithms.
2. Stable Sorting Algorithm: Counting Sort preserves the relative order of elements with equal values, making it stable and suitable for applications where stability is essential.
3. Non-Comparative Sorting: Counting Sort doesn’t rely on element comparisons, which can make it faster than comparison-based algorithms for specific data types.

Cons:

1. Requires Extra Space: Counting Sort requires additional space proportional to the range of input values (k), which can be a disadvantage if the range is large.
2. Limited to Integer Data: Counting Sort is primarily used for sorting integers or data that can be mapped to integers. It’s less suitable for floating-point numbers or strings.
3. Inefficient for Large Ranges: When the range of input values is large, Counting Sort requires a lot of space and time, making it less practical for datasets with a wide range of values.

When to Use Counting Sort

Counting Sort is a great choice when:

1. You know the range of the input values: Counting Sort performs best when the range (k) of input values is known and relatively small.
2. You need a stable sorting algorithm: If maintaining the relative order of equal elements is important, Counting Sort’s stability makes it a good choice.
3. Sorting integers: Counting Sort

Conclusion

Counting Sort is an efficient, non-comparative sorting algorithm that performs exceptionally well for datasets with a known and small range of integer values. Its linear time complexity makes it faster than comparison-based algorithms in specific cases, and its stability ensures that the relative order of equal elements is preserved. While the extra space required can be a drawback for large ranges, Counting Sort’s simplicity and speed make it a go-to option for specific applications.

Moreover, Counting Sort is often used in algorithms like Radix Sort to sort numbers by individual digits. It ensures that the sorting remains stable and efficient at each step, helping Radix Sort sort large datasets of numbers quickly.

Congratulations on reading to the end of the tutorial!

Read the following articles to learn how to implement Counting Sort:

In Python – How to do Counting Sort in Python

In C++ – How to do Counting Sort in C++

Have fun and happy researching!