Counting

Counting Sort is an efficient, non-comparison-based sorting algorithm suitable for sorting integers when the range of the elements to be sorted is known beforehand.

It works by counting the number of occurrences of each unique element in the input array and then using these counts to place each element in its correct sorted position.

pseudocode:

CountingSort(array, size)
    max_val = maximum value in array
    count_array[max_val + 1] = {0} // Initialize count array with zeros

    // Count occurrences of each element
    for i from 0 to size - 1
        count_array[array[i]] += 1

    // Reconstruct the sorted array
    index = 0
    for i from 0 to max_val
        while count_array[i] > 0
            array[index] = i
            index += 1
            count_array[i] -= 1

function countingSort(array) {
    // Find the maximum value in the array
    let max = Math.max(...array);

    // Create a count array to store the occurrences of each value
    let countArray = new Array(max + 1).fill(0);

    // Count occurrences of each element
    for (let i = 0; i < array.length; i++) {
        countArray[array[i]]++;
    }

    // Reconstruct the sorted array
    let sortedArray = [];
    for (let i = 0; i <= max; i++) {
        while (countArray[i] > 0) {
            sortedArray.push(i);
            countArray[i]--;
        }
    }

    return sortedArray;
}

// Example usage:
let unsortedArray = [3, 1, 6, 2, 3, 6, 2, 1];
let sortedArray = countingSort(unsortedArray);
console.log(sortedArray); // Output: [1, 1, 2, 2, 3, 3, 6, 6]

In this example:

1. countingSort function takes an array arr as input and returns a sorted array.

2. It first finds the maximum value in the input array to determine the range of values.

3. It creates an array counts to store the count of occurrences of each element.

4. It counts the occurrences of each element in the input array.

5. It modifies the counts array to store the position of each element in the sorted array.

6. It creates a sorted array sortedArr using the counts array.

The time 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 the input.

However, it requires extra space proportional to the range of the input array.