Scroll Progress Bar

Counting sort

Counting sort is a non-comparison-based sorting algorithm that works by counting the frequency of each element in the input array and then using that information to place each element in its correct sorted position. It is efficient for sorting integers within a known range. Here's a C++ implementation of counting sort with comments and Sample Output:

Program:

    #include <iostream>
    #include 
    
    // Function to perform counting sort
    void countingSort(std::vector& arr) {
        int maxElement = *std::max_element(arr.begin(), arr.end()); // Find the maximum element in the array
    
        // Create a count array to store the count of each element
        std::vector count(maxElement + 1, 0);
    
        // Count the occurrences of each element in the input array
        for (int num : arr) {
            count[num]++;
        }
    
        // Update the count array to contain the correct position of each element in the sorted array
        for (int i = 1; i <= maxElement; i++) {
            count[i] += count[i - 1];
        }
    
        // Create a temporary array to hold the sorted output
        std::vector output(arr.size());
    
        // Place each element in its correct sorted position in the output array
        for (int i = arr.size() - 1; i >= 0; i--) {
            output[count[arr[i]] - 1] = arr[i];
            count[arr[i]]--;
        }
    
        // Copy the sorted output back to the original array
        for (int i = 0; i < arr.size(); i++) {
            arr[i] = output[i];
        }
    }
    
    int main() {
        std::vector arr = {4, 2, 2, 8, 3, 3, 1};
    
        std::cout << "Original array: ";
        for (int num : arr) {
            std::cout << num << " ";
        }
    
        // Perform counting sort
        countingSort(arr);
    
        std::cout << "\nSorted array: ";
        for (int num : arr) {
            std::cout << num << " ";
        }
    
        return 0;
    }
In this code:
  • countingSort is a function that takes the input vector arr and sorts it using counting sort.
  • The algorithm first finds the maximum element in the input array to determine the range of values.
  • It then creates a count array to store the count of each element in the input array.
  • After counting the occurrences of each element, it updates the count array to contain the correct position of each element in the sorted array.
  • A temporary output array is used to place each element in its correct sorted position.
  • Finally, the sorted output is copied back to the original input array.
Sample Output:

    Original array: 4 2 2 8 3 3 1 
    Sorted array: 1 2 2 3 3 4 8
As shown in the sample output, the input vector is successfully sorted using counting sort.

question

answer

question2

answer2