Counting Sort C++

Counting Sort is an algorithm used to sort a collection of integers in linear time. It works by counting the occurrences of each unique element in the input array and using this information to determine the correct position of each element in the output array.

The steps involved in Counting Sort are as follows:

1. Find the maximum element in the input array: Iterate through the input array to find the maximum element. This step is necessary to determine the size of the count array.

2. Create a count array: Create an array called "count" with a size equal to the maximum element plus one. Initialize all elements of the count array to zero.

3. Count the occurrences of each element: Iterate through the input array and increment the corresponding count array element for each element encountered. For example, if the input array contains the element 3, increment the count[3] by 1.

4. Calculate the cumulative sum: Modify the count array by calculating the cumulative sum. Each element of the count array should store the sum of its value and the value of the previous element. This step helps determine the correct position of each element in the output array.

5. Build the output array: Create an output array with the same size as the input array. Iterate through the input array in reverse order. For each element encountered, find its corresponding position in the output array using the count array. Decrement the count array value by 1 each time an element is placed in the output array.

6. Copy the elements to the output array: Iterate through the input array again, this time in the original order. For each element encountered, find its corresponding position in the output array using the count array. Place the element in the correct position in the output array.

7. Return the sorted array: After all elements have been placed in the output array, return the sorted array.

Counting Sort has a time complexity of O(n + k), where n is the number of elements in the input array and k is the range of the input elements. It is efficient when the range of elements is small compared to the number of elements to be sorted.

Here is an example implementation of Counting Sort in C++:

#include <iostream>
#include <vector>

void countingSort(std::vector<int>& arr) {
    int maxElement = *max_element(arr.begin(), arr.end());
    std::vector<int> count(maxElement + 1, 0);

    for (int num : arr) {
        count[num]++;
    }

    for (int i = 1; i <= maxElement; i++) {
        count[i] += count[i - 1];
    }

    std::vector<int> output(arr.size());

    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    arr = output;
}

int main() {
    std::vector<int> arr = {4, 2, 2, 8, 3, 3, 1};

    countingSort(arr);

    for (int num : arr) {
        std::cout << num << " ";
    }

    return 0;
}

This implementation uses the <vector> header for dynamic arrays and the max_element function from the <algorithm> header to find the maximum element in the input array. The input array is sorted in-place using the Counting Sort algorithm. Finally, the sorted array is printed to the console.