계수정렬(Counting Sort)

계수정렬(Counting Sort)

개념

• 각 숫자가 몇 개 있는지 개수를 세어 저장한 후에 정렬
• 기수정렬과 마찬가지로 비교를 하지 않는 알고리즘 
• 양수만 가능, 값의 범위가 제한적 

과정

 

1. 정렬되지 않은 배열의 수들이 각각 몇 번 나왔는지 count 배열에 기록

# 정렬을 수행할 배열
arr = [4, 7, 9, 1, 3, 5, 2, 3, 4]

count = [0] * (max(arr) + 1)

for num in arr:
    count[num] += 1
    
print(count)

# [0, 1, 1, 2, 2, 1, 0, 1, 0, 1]

 

2. count 배열을 앞에서 순회하여 자신이 정렬된 배열에서 몇 번째에 나와야 하는지 기록하기 위해 누적합으로 갱신 

for i in range(1, len(count)):
    count[i] += count[i-1]

print(count)

# [0, 1, 2, 4, 6, 7, 7, 8, 8, 9]

 

3. arr의 원소를 정렬하기 위해 길이가 같은 result 배열 생성 

result = [0] * (len(arr))

for num in arr:
    idx = count[num]
    result[idx - 1] = num
    count[num] -= 1

print(result)

 

시간 복잡도

• O(N+K) => 정렬해야하는 원소의 수(N), 배열 내 최대값(K)