카운팅 정렬 (Counting Sort)

---

카운팅 정렬은 비교 기반이 아닌 분포 기반의 정렬 알고리즘입니다. 정렬하려는 데이터의 크기가 제한적일 때 매우 효율적으로 동작하며, 시간 복잡도가 $O(n)$입니다.
특히 정렬할 데이터의 범위가 좁고, 데이터가 중복되어 있을 때 강력한 성능을 발휘합니다.

카운팅 정렬의 특징

---

• 시간 복잡도: $O(n + k)$, 여기서 n은 데이터의 개수, k는 데이터의 값의 범위입니다.

• 공간 복잡도: $O(n + k)$, 카운팅 배열을 위한 추가 공간이 필요합니다.

• 제자리 정렬이 아님: 입력 데이터를 수정하지 않고 별도의 결과 배열에 데이터를 저장합니다.

• 안정 정렬: 입력 데이터의 순서를 유지합니다.

카운팅 정렬의 동작 과정

---

1. 입력 배열 생성

정렬하려는 데이터(입력 배열)를 준비합니다.
예시로 [4, 2, 2, 8, 3, 3, 1] 로 구현하겠습니다.

입력 배열

index	0	1	2	3	4	5	6
element	4	2	2	8	3	3	1

2. 카운팅 배열 생성

데이터의 범위에 따라 카운팅 배열을 생성하고, 각 값이 몇 번 등장하는지 카운팅합니다.
입력 배열에서 각 요소의 빈도수를 카운팅 배열의 인덱스에 기록합니다.

카운팅 배열

index	0	1	2	3	4	5	6	7	8
count	0	1	2	2	1	0	0	0	1

위에서 알 수 있듯이

• 값 1은 1번
• 값 2는 2번
• 값 3은 2번
• 값 4는 1번
• 값 8은 1번 등장했습니다.

3. 카운팅 배열의 누적합 계산

카운팅 배열을 누적합으로 변환합니다. 각 값의 누적합은 정렬된 배열에서 해당 값이 차지할 마지막 위치를 가리킵니다.
즉, 누적합을 사용하면 입력 배열의 각 값이 정렬된 배열에서 어디에 위치할지를 계산할 수 있습니다.

카운팅 배열의 누적합

index	0	1	2	3	4	5	6	7	8
count	0	1	3	5	6	6	6	6	7

• 값 1은 정렬된 배열에서 첫 번째 위치(인덱스 0)를 차지
• 값 2는 두 번째와 세 번째 위치(인덱스 1과 2)에 위치
• 값 3은 네 번째와 다섯 번째 위치(인덱스 3과 4)에 위치합니다.

4. 결과 배열 생성

1. 카운팅 배열의 누적합을 사용해 입력 배열을 다시 순회하며 정렬된 결과 배열을 생성합니다.
   이 과정에서 카운팅 배열의 값을 1씩 감소시키며, 각 값을 올바른 위치에 배치합니다.

2. 입력 배열의 마지막 요소부터 순회하여, 해당 값을 카운팅 배열의 누적합 값에서 1을 뺀 위치에 배치합니다.
   카운팅 배열의 해당 값을 1씩 감소시킵니다.

for (int i = n - 1; i >= 0; i--) {
    result[counting[input[i]] - 1] = input[i];
    counting[input[i]]--;
}

최종적으로 정렬된 결과 배열은 다음과 같습니다.

정렬된 결과 배열

index	0	1	2	3	4	5	6
result	1	2	2	3	3	4	8

5. 전체 코드

#include <stdio.h>

void counting_sort(int arr[], int n) {
    int counting[10001] = {0};  // 카운팅 배열 초기화
    int result[n];  // 정렬된 결과를 저장할 배열

    // 카운팅 배열 초기화 (각 값의 빈도를 저장)
    for (int i = 0; i < n; i++) {
        counting[arr[i]]++;
    }

    // 카운팅 배열을 누적합으로 변환
    for (int i = 1; i < 10001; i++) {
        counting[i] += counting[i - 1];
    }

    // 입력 배열을 역순으로 순회하며 정렬
    for (int i = n - 1; i >= 0; i--) {
        result[counting[arr[i]] - 1] = arr[i];
        counting[arr[i]]--;  // 카운팅 값을 1 감소
    }

    // 결과 출력
    for (int i = 0; i < n; i++) {
        printf("%d\n", result[i]);
    }
}

int main() {
    int n;
    scanf("%d", &n);  // 입력 크기

    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);  // 입력 배열
    }

    counting_sort(arr, n);  // 카운팅 정렬 실행
    return 0;
}

카운팅 정렬 요약

1. 카운팅 배열 생성: 입력 배열에서 각 값의 빈도를 카운팅 배열에 저장

2. 누적합 계산: 카운팅 배열을 변환하여 각 값이 정렬된 배열에서 어느 위치에 들어갈지 결정

3. 결과 배열 생성: 카운팅 배열의 누적합을 사용해 입력 배열을 순회하며 정렬된 배열을 생성

4. 시간 복잡도: $O(n + k)$로, 입력 데이터의 개수와 값의 범위에 비례한 성능을 가짐

카운팅 정렬은 데이터의 범위가 한정적이고 중복된 값이 많을 때, 매우 효율적으로 동작하는 정렬 알고리즘입니다.
이를 통해 큰 입력 데이터를 빠르게 처리할 수 있습니다.