정렬 알고리즘 3 : 계수 정렬(Counting sort)

세 번째로 알아볼 정렬 알고리즘은 바로 계수 정렬!

계수 정렬은 수의 범위가 적을 때 사용하면 좋은 정렬 알고리즘으로 배열의 가장 큰 값에 따라 시간 복잡도가 달라진다.

배열의 가장 큰 값이 k라고 한다면 O(n+k)의 시간 복잡도를 갖는다.

즉, 입력에 비해서 원소들의 값의 범위가 적다면 계수정렬을 사용하는 것이 효율적인 방법이 될 수 있다!

 

 

방법

1. 입력된 배열중 가장 큰 값(k) 찾기

2. k+1 크기의 0으로 초기화된 배열 생성한다. 이는 입력된 배열의 원소가 각각 몇 개가 있는지 셀 배열이다.

3. 배열의 원소를 하나씩 검사하여 2번에서 생성한 배열의 인덱스에 해당하는 값을 1씩 올려준다.
(즉, 각 값이 몇 개가 나왔는지 카운팅 해준다.)

4. 각 인덱스를 값만큼 반복하여 출력한다. 

 

 

 

예시

배열 :  4 3 2 3 0 1 2 5 4 1 

1. 입력된 배열 중 가장 큰 값(k)은 5

2. 0으로 초기화된 6 크기의 배열을 생성한다.

index = 0	index = 1	index = 2	index = 3	index = 4	index = 5
0	0	0	0	0	0

3. 배열을 하나씩 확인하여 개수를 세어준다.

배열 :  4 3 2 3 0 1 2 5 4 1 

index = 0	index = 1	index = 2	index = 3	index = 4	index = 5
0	0	0	0	1	0

배열 :  4 3 2 3 0 1 2 5 4 1 

index = 0	index = 1	index = 2	index = 3	index = 4	index = 5
0	0	0	1	1	0

배열 :  4 3 2 3 0 1 2 5 4 1 

index = 0	index = 1	index = 2	index = 3	index = 4	index = 5
0	0	1	1	1	0

배열 :  4 3 2 3 0 1 2 5 4 1 

index = 0	index = 1	index = 2	index = 3	index = 4	index = 5
0	0	1	2	1	0

배열 :  4 3 2 3 0 1 2 5 4 1 

index = 0	index = 1	index = 2	index = 3	index = 4	index = 5
1	0	1	2	1	0

배열 :  4 3 2 3 0 1 2 5 4 1 

index = 0	index = 1	index = 2	index = 3	index = 4	index = 5
1	1	1	2	1	0

배열 :  4 3 2 3 0 1 2 5 4 1 

index = 0	index = 1	index = 2	index = 3	index = 4	index = 5
1	1	2	2	1	0

배열 :  4 3 2 3 0 1 2 5 4 1

index = 0	index = 1	index = 2	index = 3	index = 4	index = 5
1	1	2	2	1	1

배열 :  4 3 2 3 0 1 2 5 4 1

index = 0	index = 1	index = 2	index = 3	index = 4	index = 5
1	1	2	2	2	1

배열 :  4 3 2 3 0 1 2 5 4 1

index = 0	index = 1	index = 2	index = 3	index = 4	index = 5
1	2	2	2	2	1

4. 각 인덱스를 값만큼 반복하여 출력한다.

0 1 1 2 2 3 3 4 4 5

 

깔끔하게 정리된 것을 확인할 수 있다.

 

 

---

구현(파이썬)

#https://teching.tistory.com/
def countingSort(list):
    k = max(list)
    cntNum = [0] * (k+1)
    for n in list :
        cntNum[n] += 1
    new = []
    for i in range(len(cntNum)):
        new += [i]*cntNum[i]
    return new

nums = [4, 3, 2, 3, 0, 1, 2, 5, 4, 1]
sortedNum = countingSort(nums)
print(sortedNum)