[알고리즘] 카운팅 정렬(Counting sort)

카운팅 정렬(Counting sort)

비교 기반 정렬 알고리즘이 아닌 정수 정렬 알고리즘 중 하나로, 특정한 조건을 만족할 때 매우 빠른 성능을 보이는 알고리즘이다. 다른 정렬 알고리즘들과 달리 비교를 하지 않고, 정수의 개수를 세어서 정렬하는 방식으로 동작하게 된다.

입력 배열의 크기에 비례하는 메모리를 사용하므로, 입력 배열의 크기가 매우 크지 않을 때 유용하게 사용될 수 있다.

카운트 정렬의 기본적인 동작 방식은

1. 입력 배열의 각 원소의 값을 기준으로, 해당 값의 등장 횟수를 카운팅하여 저장, 이를 위해 카운팅 배열 사용
2. 카운팅 배열의 누적 합을 계산하여 정렬 결과 배열을 만든다.
3. 입력 배열을 역순으로 순회하면서 정렬 결과 배열에 값을 저장하고, 해당 값의 등장 횟수를 감소시킨다.

예시를 파이썬 코드를 통해서 설명하겠다.

예제

lst = [5,2,3,1,4,2,3,5,1,7,9]

다음과 같은 리스트가 있을 때, 카운팅 배열을 만들어 준다.

카운팅 배열

cnt = [0]*(max(lst)-min(lst)+1)
# [0, 0, 0, 0, 0, 0, 0, 0, 0]

먼저 리스트의 최대값과 최소값의 차에 +1 만큼 값이 0인 배열을 생성한다.
시간 복잡도는 입력 배열의 크기를 N, 입력 값의 최댓값과 최솟값의 범위를 M이라고 할 때, O(N + M)이다
만약 예시에서 최대값이 100이 추가된다면 10~99 사이의 의미없는 배열이 생겨 비효율적이게 된다.

for num in lst:
    cnt[num-1] += 1
# [2, 2, 2, 1, 2, 0, 1, 0, 1]

lst의 숫자를 반복문을 통해 개수가 몇 개인지 세어준다.
위의 예제에는 1이 2개, 2가 2개, …, 9개 1개이다.

카운트 배열 누적 합 계산

for i in range(1, len(cnt)):
    cnt[i] += cnt[i-1]
# [2, 2, 2, 1, 2, 0,  1,  0,  1] 값을 누적해서 더해 줌
# [2, 4, 6, 7, 9, 9, 10, 10, 11] --> 결과

정렬된 값 출력

result = [0]*len(lst)
for i in lst:
    idx = cnt[i-1]
    result[idx-1] = i
    cnt[i-1] -= 1
# result : [1, 1, 2, 2, 3, 3, 4, 5, 5, 7, 9]

결과값을 담을 result를 생성
lst에서 값을 꺼내와서 result 배열에 넣고 해당 숫자의 cnt 배열에서의 값을 1줄임

합성곱 생략

arr = [4, 2, 2, 8, 3, 3, 1]  # 입력 배열
cnt = [0] * 9  # 카운트 배열 초기화

# 카운트 배열에 배열의 원소 등장 횟수 카운팅
for num in arr:
    cnt[num] += 1

result = []
for i in range(len(cnt)):
    while cnt[i] > 0:  # 해당 값의 등장 횟수가 0보다 크면 반복
        result.append(i+min(arr))  # 결과 배열에 값을 저장
        cnt[i] -= 1  # 해당 값의 등장 횟수를 감소시킴
# [1, 2, 2, 3, 3, 4, 8]