[정렬] 계수 정렬 (카운팅 소트, Counting Sort)

계수 정렬(Counting Sort)이란

원소끼리 비교를 하지 않고 원소가 몇번 등장하는지 갯수를 세서 정렬하는 방법이다.

따라서 비교정렬이 아니고 같은 원소의 순서가 바뀌지 않는 안정정렬(stable sort)이다. 

시간복잡도는 O(n + k)으로 퀵정렬, 병합정렬에 비해 일반적으로 빠르다.

k: 정렬할 수들 중 가장 큰 값

n: 정렬할 수의 개수 

 

만약 k가 n보다 작은 수이면 O(n)이 되지만, k가 n보다 매우 큰 수이면 O(무한)이 될 수도 있다.

가장 큰 숫자에 영향을 받는다는 단점이 있다.

 

만약 정렬해야하는 리스트가 [0, 1, 9999]일때는 배열에 2부터 9998까지 불필요한 공간을 만들어야하기 때문에 비효율적이다.

또, n의 값이 너무 커지면 일반 정렬 알고리즘보다 느려질 수 있으므로 적은 개수의 숫자를 정렬할때 좋다. 

 

정렬할때 숫자 갯수를 저장할 공간(k)과 결과를 저장할 공간(n)이 필요하다. 따라서 O(n+k) 의 공간복잡도를 가진다.

 

 

 

파이썬 코드

# 정렬 전 리스트
before = [3, 4, 0, 1, 2, 4, 2, 4]

# 정렬 후 리스트
after = []

# 빈도를 저장할 공간 (before의 최대값만큼의 크기, 0으로 초기화)
li = [0 for _ in range(max(before)+1)]

# 빈도 세서 저장하기
for each in before:
    li[each] += 1

# 빈도수만큼 정렬 후 리스트에 추가
for i in range(len(li)):
    num = li[i]
    for k in range(num):
        after.append(i)

# 정렬 후 리스트 출력 
print(after)

파이썬의 append()는 O(1)이기때문에 따로 누적합을 구하지 않고 그냥 바로 append해줬다. 

 

 

 

정석 알고리즘대로 (누적합을 구하는 방식으로) 짠 코드

 

# 정렬 전 리스트
before = [3, 4, 0, 1, 2, 4, 2, 4]

# 정렬 후 리스트
after = [-1 for _ in range(len(before))]

# 빈도를 저장할 공간 (before의 최대값만큼의 크기, 0으로 초기화)
li = [0 for _ in range(max(before)+1)]

# 빈도 세서 저장하기
for each in before:
    li[each] += 1

# 누적합 구하기
for i in range(len(li)-1):
    li[i+1] += li[i]
print(li)

# 누적합을 바탕으로 숫자를 결과에 넣어주기
# 예) 누적합이 [1, 2, 4]인 경우, 0~1에 0, 1~2에 1, 2~4에 3을 넣는것
s = 0
for i in range(len(li)):
    for k in range(s, li[i]):
        after[k] = i
    s = li[i]


# 정렬 후 리스트 출력
print(after)

 

 

 

 

대표 문제

10989번: 수 정렬하기 3

 

참고한 포스팅

(Algorithm) 계수 정렬(counting sort)

카운팅 정렬, 래딕스 정렬 · ratsgo's blog