[c++] 카운팅 정렬

12 Dec 2023

카운팅 정렬(Counting Sort)은 정수 정렬 알고리즘의 하나로, 입력된 숫자들을 세어서 정렬하는 방식입니다. 이 알고리즘은 입력 숫자들이 특정 범위 내에 있을 때 가장 효율적으로 동작합니다. 여기에서는 C++을 사용하여 카운팅 정렬에 대해 설명하겠습니다.

알고리즘 설명

카운팅 정렬은 다음과 같은 단계로 진행됩니다.

입력 배열을 순회하며 각 숫자가 등장한 횟수를 세어 카운트 배열에 저장합니다.
카운트 배열을 누적으로 합산하여 각 숫자의 정렬된 위치를 계산합니다.
임시 배열을 사용하여 정렬된 결과를 생성합니다.

카운팅 정렬은 입력 배열과 카운트 배열의 크기에 비례하는 메모리 공간이 필요하며, 입력 배열의 값들이 양수인 경우에만 동작합니다.

C++ 예시

다음은 C++으로 구현된 카운팅 정렬의 예시 코드입니다.

#include <iostream>
#include <vector>

void countingSort(std::vector<int>& arr, int range) {
    std::vector<int> count(range + 1, 0);
    std::vector<int> output(arr.size(), 0);

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

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

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

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

int main() {
    std::vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
    int range = 8;
    countingSort(arr, range);

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

    return 0;
}

위 코드는 입력 배열을 카운팅 정렬하여 오름차순으로 정렬한 후 결과를 출력하는 예시입니다.

카운팅 정렬의 시간복잡도는 O(n + k)로, n은 입력 배열의 크기이고, k는 정렬할 숫자들의 범위입니다.

결론

C++을 사용하여 카운팅 정렬을 적용하여 숫자 배열을 효과적으로 정렬할 수 있습니다. 이 알고리즘은 숫자의 범위가 작을 때 가장 빠르게 동작하므로, 특히 작은 정수들을 정렬할 때 유용합니다.

참고자료

GeeksforGeeks: Counting Sort