[CLRS] [8-1] Counting Sort

1. Counting Sort?

- Counting Sort는 정수로 표현할 수 있는 데이터에 대해 효율적으로 작동하는 O(n) 정렬 알고리즘.

- 정렬의 대상이 되는 데이터 값의 범위가 명확할 때 주로 사용.

- Counting Sort는 비교 정렬 알고리즘이 아닌 분포 정렬 알고리즘이다. 

 

2. Counting Sort 알고리즘

i) 입력 배열과 범위 설정

- 주어진 입력 배열이 A라고 하고, 배열의 길이를 n이라고 하자.

- 데이터 값은 0 이상 k이하인 양수라고 가정해보자. (이때 k == max(A))

 

ii) 카운트 배열 초기화

- C라는 배열을 만들고, 길이를 k+1로 설정 (또는 max(A) - min(A)로 설정)

- C[i]는 입력 배열에서 값이 i인 요소가 몇 번 등장하는지 저장함

- C의 초기값은 전부 0 이다.

 

iii) 빈도수 계산

- 입력 배열 A를 순회하면서 각 요소의 값을 인덱스로 삼아 해당 값의 빈도를 C에 저장한다.

ex) 값이 3인 요소가 두번 등장하면 C[3] == 2 가된다.

 

iv) 누적 합 계산

- C 배열의 누적 합을 계산하여 요소들이 최종 정렬된 배열에서 위치할 인덱스를 찾는다.

- 즉, C[i]는 값이 i인 요소가 최종 정렬 배열에서 어느 위치까지 차지하는지 나타냄

ex) C[3] == 5라면, 값 3의 마지막 위치가 정렬된 배열의 5번째에 오게 된다.

 

v) 출력 배열 생성

- 정렬된 결과를 저장할 배열 B를 생성

-  원래 배열 A의 요소들을 뒤에서부터 순회하면서 각 요소를 C배열에서 지정된 위치에 놓는다.

- 각 요소를 B에 배치할 때 마다 C에서 해당 요소의 인덱스를 1씩 감소시킨다.

 

3. Counting Sort 장단점

3.1. 장점

- 비교 연산 없이 정렬하기 때문에, 데이터의 최댓값 k에 따라 O(n+k)의 시간복잡도로 정렬가능.

- 데이터의 범위가 제한되어 있고, 중복되는 값이 많으면 매우 효율적.

 

3.2. 단점

- 데이터의 값이 너무 넓거나, 데이터가 연속적일때 사용 불가.

 

4. Code 구현

def counting_sort(arr):
    min_val = min(arr)
    max_val = max(arr)
    counting_list = [0] * (max_val - min_val + 1)
    result_list = [0] * len(arr)

    # 각 요소의 빈도수 계산 
    for i in arr:
        counting_list[i - min_val] += 1
    
    # 누적합 계산
    for i in range(1, len(counting_list)): 
        counting_list[i] += counting_list[i - 1]

    # 결과 리스트에 정렬된 값 배치
    while arr:
        value = arr.pop()  # 마지막 요소를 가져와서
        result_list[counting_list[value - min_val] - 1] = value  # 결과 리스트의 위치에 배치
        counting_list[value - min_val] -= 1  # 카운트 배열 값 감소

    return result_list


arr = [1, 3, 5, 2, 2, 2, 3, 4]
print(counting_sort(arr))