[알고리즘]정렬-계수 정렬(Counting Sort)

숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.
참고교재: 쉽게 배우는 알고리즘(문병로)

기본적인 정렬 알고리즘 O(n^2)
1.선택정렬
2.버블정렬
3.삽입정렬

고급 정렬 알고리즘 O(n*logn)
1.병합정렬
2.퀵정렬
3.힙정렬

특수 정렬 알고리즘 O(n)
1.계수정렬
2.기수정렬

 

계수 정렬(Counting Sort) 이란

계수 정렬(Counting Sort)은 정수나 정수로 변환할 수 있는 자료에 대해서만 적용 가능한 효율적인 정렬 알고리즘입니다. 이 알고리즘의 작동 방식은 입력의 범위가 제한적일 때 매우 효과적이며, 시간 복잡도는 O(n)입니다.
계수 정렬의 기본 아이디어는 각 숫자를 계산(count)하고, 이를 기반으로 정렬된 배열을 생성하는 것입니다.

 

계수 정렬(Counting Sort) 과정

계수 정렬의 주요 단계는 다음과 같습니다:

1. 입력 배열을 순회하며 각 요소의 개수를 계산합니다. 이 개수는 "계수 배열"에 저장됩니다.
2.계수 배열을 누적 합으로 갱신합니다. 이렇게 하면 각 숫자가 정렬된 배열에서 어디에 위치해야 하는지 알 수 있습니다.
3.입력 배열을 역순으로 순회하며, 각 요소를 이미 정렬된 위치에 배치합니다. 이 때, 해당 요소의 계수를 1만큼 감소시킵니다.

 

계수 정렬은 입력의 범위가 작을 때 효과적입니다. 입력의 최대값이 크면, 계수 배열의 크기도 커져 메모리를 많이 사용하게 됩니다. 또한, 정수나 정수로 변환할 수 있는 자료에만 사용할 수 있는 단점이 있습니다.

하지만 이러한 제약 사항에도 불구하고, 계수 정렬은 선형 시간 복잡도를 가진다는 점에서 매우 강력한 정렬 알고리즘이라고 할 수 있습니다.

 

 

계수 정렬(Counting Sort) 코드

void countingSort(vector<int>& arr) {
    int max = *max_element(arr.begin(), arr.end());
    int min = *min_element(arr.begin(), arr.end());
    int range = max - min + 1;

    vector<int> count(range), output(arr.size());
    for(int i = 0; i < arr.size(); i++)
        count[arr[i]-min]++;

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

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

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

 

 

테스트 코드

int main() {
    vector<int> arr = {10, 2, 7, 8, 5, 3, 2, 6, 1, 9};
    countingSort(arr);
    for(int i=0; i<arr.size(); i++)
        cout << arr[i] << " ";
    return 0;
}

 

테스트 결과

1 2 2 3 5 6 7 8 9 10