카운팅 정렬 알고리즘 (Counting Sort / 계수 정렬)

포스팅에서 다룰 계수 정렬이라고도 하는 카운팅 정렬(Counting Sort)은 각 항목의 개수를 세어 저장해 두고, 그에 따라서 적절한 위치에 정렬하는 효율적인 알고리즘입니다. 오름, 내림차순 정렬 과정, 시간 복잡도, 장단점, 카운팅 정렬 파이썬 알고리즘 구현에 대해 알아보겠습니다.

 

카운팅 정렬이란? (Counting Sort)

항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세어서 적절한 위치에 선형 시간에 정렬하는 방법입니다.

 

각 항목의 개수를 기록하기 위해 정수로 인덱스 되는 카운트 리스트를 사용하기 때문에 정수나 정수로 표현할 수 있는 자료에만 적용할 수 있는 정렬 알고리즘입니다.

카운트 리스트를 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 합니다.

 

카운팅 정렬 과정

Data: 정렬할 데이터 리스트, Cnt: 카운트 리스트, Sort: 정렬된 리스트

 

1. 정렬할 데이터에서 각 항목들의 개수를 세고, 정수 항목들로 직접 인덱스 되는 카운트 리스트에 저장합니다.

> Data [2, 0, 1, 2, 3, 0, 2]  /  Cnt [2, 1, 3, 1]  (Cnt [i] = 항목 i의 개수)

 

2. 정렬된 집합에서 각 항목의 앞에 위치할 항목의 개수를 반영하기 위해

2-1) 오름차순: Cnt의 원소에 앞의 항목의 개수를 더합니다.

> Cnt = [2, 3, 6, 7]  ->  0은 1~2번째, 1은 3번째, 2는 4~6번째, 3은 7번째 위치에 정렬

 

2-2) 내림차순: Cnt의 원소에 뒤의 항목 개수를 더합니다.

> Cnt = [7, 5, 4, 1]  ->  0은 6~7번째, 1은 5번째, 2는 2~4번째, 3은 1번째 위치에 정렬

 

3. 데이터의 마지막 항목부터 원소를 정렬합니다. (오름차순 예시)

1. 마지막 원소가 2이므로 Cnt [2]의 값이 6이므로 Sort의 6번째 위치에 2를 삽입하고 Cnt [2]의 값을 1 감소시킵니다.
   Sort = [ ,  ,  ,  ,  , 2, ]
2. 뒤에서 두 번째 원소가 0이므로 Cnt [0]의 값이 2이므로 Sort의 2번째 위치에 0을 삽입하고 Cnt [0]의 값을 1 감소시킵니다.
   Sort = [ , 0, , , , 2, ]
3. 뒤에서 세 번째 원소가 3이므로 Cnt [3]의 값이 7이므로 Sort의 7번째 위치에 3을 삽입하고 Cnt [3]의 값을 1 감소시킵니다.
   Sort = [ , 0, , , , 2, 3]
4. 데이터의 첫 항목까지 과정을 반복하면 계수 정렬 오름차순이 끝납니다.
   Sort = [0, 0, 1, 2, 2, 2, 3]

시간 복잡도와 장단점

• 평균 수행 시간: O(n+k)
• 최악 수행 시간: O(n+k)
• n: 리스트 개수, k: 정수의 최댓값
• n이 k보다 클 경우 시간 복잡도: O(n)
• 장점: 적은 개수의 숫자를 정렬할 때 빠른 속도로 정렬이 가능하고, 비교를 하지 않는 안정된 정렬이다.
• 단점: 항목 개수를 저장할 공간, 결과를 저장할 공간 등 추가적인 메모리가 필요하다.

계수 정렬 알고리즘 코드

• a [] - 정렬할 데이터 리스트
• sorted_list [] - 정렬된 데이터 리스트
• cnt [] - 각 항목의 개수를 저장한 리스트

def counting_sort(list, s_list):
    cnt = [0] * (max(list) + 1)

    # 각 항목의 개수 저장
    for i in list:
        cnt[i] += 1

    # 오름차순
    for idx in range(1, len(cnt)):
        cnt[idx] += cnt[idx - 1]

    # 내림차순
    # for idx in range(len(cnt) - 2, -1, -1):
    #     cnt[idx] += cnt[idx + 1]

    # 적절한 위치에 저장
    for j in range(len(list) - 1, -1, -1):
        s_list[cnt[list[j]] - 1] = list[j]
        cnt[list[j]] -= 1

a = [2, 0, 1, 2, 3, 0, 2]
sorted_list = [0] * len(a)
counting_sort(a, sorted_list)
print(sorted_list)

---

카운팅 정렬 파이썬으로 구현해보고, 계수 정렬의 장점, 단점, 과정, 시간 복잡도, 카운팅 정렬 오름차순, 내림차순 알고리즘까지 알아보았습니다.