계수정렬(count sort)

계수정렬(count sort)

---

데이터의 빈도수(계수)를 기반으로 정렬
원리

1. 최대값 찾기
2. 카운트 배열 초기화
3. 빈도 계산
4. 누적 합 계산
5. 출력 배열에 정렬된 값 배치
6. 결과 복사
7. 메모리 해제

pseudocode

계수정렬(array : 배열, size : 배열 크기)

    1. 배열에서 가장 큰 값을 찾기
    2. 카운트 배열 초기화
    3. 배열의 각 요소에 대한 빈도 계산하여 카운트 배열에 저장
    4. 카운트 배열의 누적합 계산
    5. 출력 배열에 각 요소를 카운트 배열을 기반으로 배치
    6. 출력 배열을 원래 배열에 복사하여 정렬 완료

best case 시간복잡도 : $O(n)$
avg case 시간복잡도 : $O(n)$
worst case 시간복잡도 : $O(n)$
안정성 : 안정
장점 : $O(n)$ 이라는 매우 효율적 (기수정렬 응용)
단점 : 카운팅배열의 저장할 공간 필요, 정렬된 배열을 저장할 추가 배열 필요, 특수값으로 인한 카운팅배열 낭비
ex : 특수값 {1,2,3,999999} ⇒ 카운팅배열은 1부터 999999까지라는 공간 필요

실제코드

#include <stdio.h>
#include <stdlib.h>

// countSort 함수 정의
void countSort(int *array, int size) {
    
    // 배열에서 가장 큰 값을 찾기
    int max = array[0];
    for (int i = 1; i < size; i++) {
        if (array[i] > max) {
            max = array[i];
        }
    }

    // 카운트 배열 할당 및 초기화
    int *count = (int *)calloc(max + 1, sizeof(int));
    int *output = (int *)malloc(size * sizeof(int));

    // 각 요소의 빈도 계산
    for (int i = 0; i < size; i++) {
        count[array[i]]++;
    }

    // 카운트 배열의 누적합 계산
    for (int i = 1; i <= max; i++) {
        count[i] += count[i - 1];
    }

    // 출력 배열에 요소를 배치
    for (int i = size - 1; i >= 0; i--) {
        output[count[array[i]] - 1] = array[i]; //결과배열에 원본 배열의 계수 위치에 원본값 저장
        count[array[i]]--; //계수의 개수 감소
    }

    // 정렬된 값을 원래 배열에 복사
    for (int i = 0; i < size; i++) {
        array[i] = output[i];
    }

    // 메모리 해제
    free(count);
    free(output);
}

int main(int argc, const char * argv[]) {
    int arr[20] = {
        3, 5, 2, 2, 4,
        6, 1, 3, 7, 8,
        2, 11, 2, 21, 20,
        12, 14, 1, 6, 16
    };
    int n = sizeof(arr) / sizeof(int);
    countSort(arr, n);
    // 정렬된 배열 출력
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}