[정렬] 계수 정렬

 

계수 정렬이란?

• 특정 조건이 부합할 때만 사용할 수 있지만, 매우 빠르게 동작하는 정렬 알고리즘
• 데이터 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능
• counting 값을 저장할 새로운 배열 공간이 필요함
• 비교정렬 X
• 안정정렬

 

시간 복잡도

• 모두 O(N+K) (데이터 개수 = N, 데이터 중 최댓값 =  K)

 

언제 사용하면 좋을까?

• 때에 따라서 비효율적임
• 데이터가 0, 999999 와 같이 2개의 숫자가 있을 때, 정렬할 데이터는 적지만 1000000크기를 지닌 counting 배열을 생성해야 된다.
• 따라서, 동일한 값을 가지는 데이터가 여러 번 등장할 때 사용하면 좋음

 

구현 코드

int main () {
    int arr[] = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2};
    int size = 15;

    // [step 0] : 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담기는 리스트 생성
    int n = *max_element(arr, arr+size) + 1;
    vector<int> count(n, 0);

    // [step 1] : 데이터를 하나씩 확인해 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가
    for (int i = 0; i < size; i++) {
        count[arr[i]]++;
    }

    // [step 2] : count 어레이에 입력된 데이터 확인 및 출력
    for (int i = 0; i < n; i++) {
        // 개수만큼 출력 
        for (int j = 0; j < count[i]; j++) {
            cout << i << " ";
        }
    }

    return 0;
}