Lecture 353:- Count Sort

Counting Sort is an integer sorting algorithm that works well for sorting elements within a limited range. It is not a comparison-based sorting algorithm, which means it does not directly compare elements to sort them. Instead, it counts the occurrences of each element in the input array and uses this information to construct the sorted output.

Here's how the Counting Sort algorithm works:

1. Find the maximum element (max) in the input array.
2. Create a counting array (count[]) of size (max + 1) and initialize all elements to 0. The count[i] will store the number of occurrences of element i in the input array.
3. Traverse the input array and count the occurrences of each element. Increment count[arr[i]] for each element arr[i].
4. Modify the count array to store the cumulative sum of counts. Each element count[i] will now store the number of elements less than or equal to i.
5. Create an output array (output[]) of the same size as the input array.
6. Traverse the input array again from the end, and for each element arr[i], place it at the correct position in the output array based on the count array. Decrease count[arr[i]] after placing the element.
7. The output array now contains the sorted elements.

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.