계수 정렬(Counting Sort)

계수 정렬(Counting Sort) → O(N)

- 숫자가 등장한 횟수를 세서 그 기준으로 정렬하는 방법

- 정렬하는 숫자가 특정한 범위안에 있을 때 사용할 수 있습니다.

   + 메모리 낭비가 있을 수 있습니다.

- 비교나 위치 교환 없이 정렬이 가능.

 

시뮬레이션

Array = [2, 4, 3, 0, 2, 3, 0, 3]

▷ 각 숫자의 등장 횟수

『 0 』 → 2번

『 1 』 → 0번

『 2 』 → 2번

『 3 』 → 3번

『 4 』 → 1번

　

구현

[C 언어 코드]

#include <stdio.h>
 
void countingSort(int arr[], int n, int count[]) {
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }
}
 
void main() {
    
    int n = 8;
    int arr[8] = { 2, 4, 3, 0, 2, 3, 0, 3};
    
    int count[5];
    for (int i = 0; i < 5; i++) {
        count[i] = 0;
    }
    countingSort(arr, n, count);
    
    for (int i = 0; i < 5; i++) {
        // 등장한 횟수를 출력
        printf("%d ", count[i]);
    }
}

 

　

시간 복잡도

계수 정렬의 시간복잡도는 O(N + K) 입니다. 

K는 정렬할 수들 중에 가장 큰 값을 의미합니다.

- K가 N보다 작은 수이면, O(N) 

- K가 N보다 매우 큰 수이면, O(무한)

  ex) N = 10, K = 100 → O(N2)

 

 

Reference

- 접미사 배열(Suffix Array)  

접미사 배열(Suffix Array)

- [BOJ] 2108 통계학