[c++] 카운팅정렬

12 Dec 2023

카운팅 정렬(Counting sort)은 정렬 알고리즘 중 하나로, 정수들의 배열을 정렬하는데 사용된다. 이 알고리즘은 입력 배열의 값들이 양의 정수일 때 가장 잘 동작하며, 작은 범위의 정수들에 대해서 빠른 성능을 보여준다.

알고리즘

입력 배열의 요소들을 순회하며 각 요소의 값을 세어준다.
카운트된 값을 기반으로 정렬된 배열을 만든다.

예제

#include <iostream>
#include <vector>
using namespace std;

void countingSort(vector<int>& arr) {
    int maxVal = *max_element(arr.begin(), arr.end());
    vector<int> count(maxVal + 1, 0);
    vector<int> result(arr.size());

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

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

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

    arr = result;
}

int main() {
    vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
    countingSort(arr);
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

위의 예제는 카운팅 정렬을 사용하여 주어진 배열을 정렬하는 C++ 코드이다.

카운팅 정렬은 입력 배열의 크기에 비례하는 메모리를 사용하며, 정수의 범위가 클수록 유리하다.