계수 정렬 Counting sort

계수정렬 (Counting sort) 은 주어진 요소들의 값에 따라 가장 효율적인 정렬 알고리즘이 될 수 있는 아주 중요한 정렬 방법이다.

기존의 효율적인 정렬방법 퀵정렬, 병합정렬, 힙정렬 들은 모두 두 요소를 비교하는 방식으로 정렬을 수행하고 이러한 정렬을 비교 정렬이라함.

⚠️ 비교 정렬의 한계..

비교 정렬들은 아무리 방법을 발전시켜도 시간복잡도가 최상의 경우일때 `O(nlogn)`일 수 밖에 없는 이론적인 한계를 가지고 있음.

• 이유 !!

  비교 연산의 이진 트리: 비교 정렬은 이진 트리 구조로 비교 연산을 수행함.
  이때 각 노드는 두 요소를 비교하는 비교 연산을 의미하고 따라서 비교 정렬은 정렬되는 요소의 크기에 따라 이진 트리의 깊이가 결정되게되므로 최소 n*log(n)의 비교가 필요함.
  
  

---

👨‍💻 계수 정렬 구현

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

void countingSort(int arr[], int n) {
    // 입력 배열에서 최댓값 찾기
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }

    // 카운팅 배열을 최댓값 크기만큼 생성하고 0으로 초기화
    int *count = (int *)calloc(max + 1, sizeof(int));

    // 입력 배열에서 각 요소의 개수 세기
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    // 정렬된 배열을 만들기 위한 인덱스 변수
    int sortedIndex = 0;

    // 카운팅 배열을 사용하여 정렬된 배열 생성
    for (int i = 0; i <= max; i++) {
        while (count[i] > 0) {
            arr[sortedIndex] = i;
            sortedIndex++;
            count[i]--;
        }
    }

    // 동적 할당한 메모리 해제
    free(count);
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    countingSort(arr, n);

    printf("정렬된 배열: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

---

⏳ 계수 정렬의 시간복잡도

기본적으로 배열의 크기 N에 비례하는 부분이 시간 복잡도에 가장 큰 영향을 미치므로, 계수 정렬의 시간 복잡도는 O(N)이다.
하지만 최댓값 K는 카운팅 배열의 크기를 결정하므로, K가 큰 경우에는 카운팅 배열을 생성하는 과정에서 시간이 추가로 소요될 수 있다.
따라서, K가 크면 최악의 경우에 시간 복잡도는 O(N + K)가 될 수 있다.

비교 정렬의 3가지 단계에서 시간 복잡도를 요약해보자.

1. 카운팅 배열 생성 단계:

• 시간 복잡도: O(N)
• 이 과정에서 카운팅 배열의 크기가 최댓값에 의해 결정. 최댓값을 찾는 과정에서 전체 요소를 한번 돌게됨.

2. 카운팅 배열에 개수 세는 단계:

• 시간 복잡도: O(N)
• 이 단계에서는 주어진 배열의 크기 N에 비례하여 각 요소의 개수를 카운팅 배열에 저장.

3. 정렬된 배열 생성 단계:

• 시간 복잡도: O(K)
• 정렬된 배열을 생성하는 단계에서, 각 요소의 개수에 따라 요소를 정확히 정렬하여 배치. 이 작업은 주어진 배열의 크기 N에 비례하여 수행.

따라서, 계수 정렬의 전체 시간 복잡도는 O(N) + O(N) + O(K) = O(2N + K) 즉, O(N + K) 이라고 할 수 있다.

코드 구현 방법에 따라 전체 시간복잡도가 살짝 다를수 있지만 Big O 표기법으로 간단히 하면 같은 값을 가진다.

---