[알고리즘] Counting Sort

Counting Sort

데이터의 크기 범위가 양의 정수이며, 값의 범위가 메모리 사이즈를 넘지 않는 경우

값을 카운팅해 정렬하는 알고리즘

---

Process

1. 최댓값을 찾는다

2. 최댓값 + 1 크기의 카운팅 배열을 만든다

3. 데이터를 카운팅 배열의 인덱스와 매핑해 갯수를 센다

4. 카운팅 배열을 조회하며 카운트만큼 출력한다

---

Code

numbers = [1, 0, 3, 2, 4, 3, 2, 2, 1, 1, 1, 1, 5, 3, 3, 4, 5]
k = 5
counts = []
result = []

length = len(numbers)
counts = [0] * length

for num in numbers:
    counts[num] += 1

for num, cnt in enumerate(counts):
    for _ in range(cnt):
        result.append(num)

print(result)

---

Time Complexity

테이터 개수가 N, 최댓값이 K일 때

최악의 경우에도 수행 시간 O(N+K)를 보장한다

 

Space Complexity

별도의 카운팅 배열이 필요하다 O(K)