[c++] 카운팅 정렬(Counting Sort) 알고리즘

08 Dec 2023

카운팅 정렬(Counting Sort) 알고리즘은 원소의 크기가 일정한 경우에 빠르게 정렬하는 알고리즘 중 하나입니다. 이 알고리즘은 각 값의 출현 횟수를 세어 정렬하는 방식으로 동작합니다.

알고리즘 설명

카운팅 정렬 알고리즘은 다음과 같은 단계로 동작합니다.

입력 배열을 순회하며 각 값의 출현 횟수를 센다.
출현 횟수를 누적하여 뒤에서부터 정렬된 위치를 계산한다.
정렬된 위치에 값을 배치하고 출현 횟수를 감소시킨다.

카운팅 정렬 알고리즘은 추가적인 공간을 사용하여야 하지만, 시간 복잡도가 O(n)으로 매우 효율적입니다.

C++ 코드 예제

#include <iostream>
#include <vector>

void countingSort(std::vector<int>& arr) {
    int maxVal = *std::max_element(arr.begin(), arr.end());
    std::vector<int> count(maxVal + 1, 0);
    std::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() {
    std::vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
    countingSort(arr);

    std::cout << "Sorted array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

위 코드는 C++을 이용하여 카운팅 정렬 알고리즘을 구현한 예제입니다.

참고 자료

Introduction to the Design and Analysis of Algorithms, Anany Levitin, 2011.
카운팅 정렬 - 위키백과