[알고리즘] 계수 정렬 (Counting Sort)

 

이전글 : )

[알고리즘] 정렬 알고리즘 (Sorting Algorithm)

 

---

 

백준 10989번 (수 정렬하기 3)을 해결하다 계수 정렬을 알게 되었습니다.

 

10989번: 수 정렬하기 3

위 문제는 메모리 제한이 8MB라는 조건이 있었습니다.

이전 글에 있는 정렬 방식들과 같이 모든 수를 입력받아 모든 수를 비교해보는 방식의 정렬을 사용하게 되면

메모리를 초과하게 됩니다.

이를 해결하기 위해서 계수 정렬을 사용 한다는 것을 알게 되었습니다.

 

---

https://efficientalgorithms.blogspot.com/2016/09/lenear-sorting-counting-sort.html

 

 계수 정렬 counting sort 

 

계수 정렬은 이름과 같이 단순하게 해당 데이터가 몇 개인지 counting을 해 정렬과 같은 효과를 볼 수 있도록 해주는 정렬 방법입니다.

시간 복잡도는 이전에 소개한 알고리즘들 보다 빠른 O(n)을 갖습니다.

입력의 개수가 아닌 크기에 영향을 받습니다. 즉 최대값의 크기가 큰 경우 매우 비효율적입니다.

따라서 입력 데이터가 작은 범위 내에서 한정적인 경우에만 사용하는 것이 좋습니다.

최댓값을 max index로 설정해야 되기에 최댓값이 얼마인지 알고 있어야 합니다.

 

---

 

 원리 

 

 

Input Data

1

8

6

4

4

6

0

3

2

2

 

Count Array

index	0	1	2	3	4	5	6	7	8
count	1	1	2	1	2	0	2	0	1

 

Sorted Data

0

1

2

2

3

4

4

6

6

8

 

위 Input Data인 { 1, 8, 6, 4, 4, 6, 0, 3, 2, 2 }와 같은 배열이 있을 때 기존의 정렬 알고리즘과 같은 경우에는 size = 10이기 때문에 크기가 10에 영향을 받지만, 계수 정렬을 사용하면 최댓값이 8이고, 최댓값 8에 대한 영향만 받게 됩니다.

 

가장 먼저 최대값의 사이즈로 배열을 만듭니다. 이는 정렬하고자 하는 데이터의 최댓값을 알아야 하는 이유입니다.

입력 데이터를 순회하면서 count array에 위와 같이 기록을 합니다.

기록한 배열을 순회하면서 배열의 원소들을 체크된 개수만큼 출력합니다.

 

 

 예제 

# 계수 정렬 코드 예제

def countingSrot(arr, K):
    c = [0] * K
    result = [0] * len(arr)
    
    for i in arr:
        c[i] += 1
    
    for i in range(1,K):
        c[i] += c[i-1]
   
    for i in range(len(arr)):
        result[c[arr[i]]-1] = arr[i]
        c[arr[i]] -= 1
​
    return result
        
arr = [1, 8, 6, 4, 4, 6, 0, 3, 2, 2]
print(countingSort(arr, 10))

 

 

---

​

[알고리즘] 백트래킹 알고리즘 ( BackTracking Algorithm )