How to use counting sort algorithm in C++

How to use the counting sort algorithm in C

The counting sort algorithm is a relatively simple and efficient sorting algorithm, suitable for scenarios where integer sequences are sorted. Its basic idea is to determine how many elements before each element are smaller than it, thereby determining its position in the ordered array.

The steps of the counting sort algorithm are as follows:

1. Find the maximum value in the array to be sorted to determine the length of the counting array.
2. Create a count array with a length of the maximum value plus one and initialize it to 0.
3. Traverse the array to be sorted, count the number of occurrences of each element, and save the statistical results to the count array.
4. Transform the counting array so that the value of each position is equal to the sum of its previous position values.
5. Create a temporary array with the same length as the array to be sorted to save the sorting results.
6. Traverse the array to be sorted from back to front, determine the position of each element in the sorted result based on the count array, and store the elements in a temporary array.
7. Copy the results of the temporary array back to the array to be sorted to complete the sorting.

The following is a sample code for a counting sorting algorithm implemented in C language:

#include <iostream>
#include <vector>

using namespace std;

void countingSort(vector<int>& arr) {
    int max_val = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
    }

    vector<int> count(max_val + 1, 0);

    for (int i = 0; i < arr.size(); i++) {
        count[arr[i]]++;
    }

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

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

    for (int i = 0; i < arr.size(); i++) {
        arr[i] = temp[i];
    }
}

int main() {
    vector<int> arr = {5, 1, 4, 3, 2};
    countingSort(arr);

    cout << "排序后的数组：";
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

In the above code, we use an auxiliary counting array to count the occurrence of each element times, and then calculate the position of each element in the sorted result through deformation. Finally, we copy the sorted results back to the original array.

Through the above example code, we can see the implementation process of the counting sorting algorithm. Its time complexity is O(n k), where n is the length of the sequence to be sorted, and k is the maximum element value and the minimum element. Add one to the difference in value.

To sum up, the counting sort algorithm is a simple but efficient sorting algorithm, suitable for scenarios where integer sequences are sorted. By using appropriate data structures and algorithms, we can accomplish the sorting task better.

The above is the detailed content of How to use counting sort algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!