Lecture 354:- Let's Code Count Sort

Here's the C++ implementation of Counting Sort:

cppCopy code

#include <iostream> #include <vector> using namespace std; // Counting Sort function void countingSort(vector<int>& arr) {    int n = arr.size();    // Find the maximum element in the input array    int maxElement = *max_element(arr.begin(), arr.end());    // Create a counting array of size (maxElement + 1)    vector<int> count(maxElement + 1, 0);    // Count the occurrences of each element in the input array    for (int i = 0; i < n; i++) {        count[arr[i]]++;    }    // Modify the count array to store cumulative sums    for (int i = 1; i <= maxElement; i++) {        count[i] += count[i - 1];    }    // Create an output array    vector<int> output(n);    // Place elements in the output array in sorted order    for (int i = n - 1; i >= 0; i--) {        output[count[arr[i]] - 1] = arr[i];        count[arr[i]]--;    }    // Copy the sorted output array to the input array    for (int i = 0; i < n; i++) {        arr[i] = output[i];    } } // Function to display the elements of the array void display(const vector<int>& arr) {    for (int val : arr)        cout << val << " ";    cout << endl; } int main() {    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};    cout << "Original Array: ";    display(arr);    countingSort(arr);    cout << "Sorted Array: ";    display(arr);    return 0; }

In this implementation, the countingSort function performs the Counting Sort algorithm to sort the input array. When you run this code, it will display the original array and then the sorted array after applying the Counting Sort algorithm.