[알고리즘][정렬] 계수 정렬 - Counting sort

🙆‍♂️계수 정렬

---

 

주어진 배열의 값 범위가 작은 경우 빠른 속도로 정렬하는 알고리즘 입니다.

원소의 개수와 원소 최대 값이 수행시간에 영향을 줍니다.

 

 

🙋‍♂️방식

---

arr = [4,0,6,2,0,6]

이런 배열을 정렬할 때

 

🚀count 배열

---

값	2	0	1	0	1	0	2
인덱스	0	1	2	3	4	5	6

먼저 배열의 요소들을 카운팅을 하고 각 인덱스에 카운팅 값들을 갖는 count 배열을 만듭니다.

count 배열을 만들 때 0,2,4,6만 있으니 이에 대한 수만 세는 것이 아니라 가장 작은 수(0)부터 가장 큰 수(6)까지의 수를 전부 계수합니다.

 

🚀누적 count 배열

---

값	2	2	3	3	4	4	6
인덱스	0	1	2	3	4	5	6

그리고 누적 카운트 배열을 만듭니다. 

 

🚀최종 index 배열

---

값	1	1	2	2	3	3	5
인덱스	0	1	2	3	4	5	6

하지만 이 배열은 개수를 계수한 것이라 실제 인덱스보다 1이 높으므로 1을 빼주면 최종 인덱스 정보를 갖는 배열을 만들 수 있습니다.

 

🚀정렬 배열

---

마지막 정렬된 배열을 찾기 위해서는 입력 배열의 뒤에서부터 값을 찾아갈 수 있습니다.

6>0>2>6>0>4 순으로 진행됩니다.

 

현재 숫자 6을 가리키는 마지막 인덱스가 5이기에 정렬 배열에 5인덱스에 6을 넣습니다.  

값	1	1	2	2	3	3	5
인덱스	0	1	2	3	4	5	6

 

값						6
인덱스	0	1	2	3	4	5

그리고 최종 인덱스 배열의 인덱스 6 값을 하나 빼줍니다.

값	1	1	2	2	3	3	4
인덱스	0	1	2	3	4	5	6

 

 

현재 숫자 0을 가리키는 마지막 인덱스가 1이기에 정렬 배열에 1인덱스에 0을 넣습니다.  

값	1	1	2	2	3	3	4
인덱스	0	1	2	3	4	5	6

값		0				6
인덱스	0	1	2	3	4	5

그리고 최종 인덱스 배열의 인덱스 0 값을 하나 빼서 업데이트 시켜줍니다.

값	0	1	2	2	3	3	4
인덱스	0	1	2	3	4	5	6

 

현재 숫자 2을 가리키는 마지막 인덱스가 2이기에 정렬 배열에 2인덱스에 2을 넣습니다. 

값	0	1	2	2	3	3	4
인덱스	0	1	2	3	4	5	6

값		0	2			6
인덱스	0	1	2	3	4	5

그리고 최종 인덱스 배열의 인덱스 2값을 하나 빼서 업데이트 시켜줍니다.

값	0	1	1	2	3	3	4
인덱스	0	1	2	3	4	5	6

 

현재 숫자 6을 가리키는 마지막 인덱스가 4이기에 정렬 배열에 4인덱스에 6을 넣습니다.

값	0	1	1	2	3	3	4
인덱스	0	1	2	3	4	5	6

값		0	2		6	6
인덱스	0	1	2	3	4	5

그리고 최종 인덱스 배열의 인덱스 6값을 하나 빼서 업데이트 시켜줍니다.

값	0	1	1	2	3	3	3
인덱스	0	1	2	3	4	5	6

 

현재 숫자 0을 가리키는 마지막 인덱스가 0이기에 정렬 배열에 0인덱스에 0을 넣습니다.

값	0	1	1	2	3	3	3
인덱스	0	1	2	3	4	5	6

값	0	0	2		6	6
인덱스	0	1	2	3	4	5

그리고 최종 인덱스 배열의 인덱스 0값을 하나 빼서 업데이트 시켜줍니다.

값	-1	1	1	2	3	3	3
인덱스	0	1	2	3	4	5	6

 

현재 숫자 4을 가리키는 마지막 인덱스가 3이기에 정렬 배열에 3인덱스에 4을 넣습니다.

값	-1	1	1	2	3	3	3
인덱스	0	1	2	3	4	5	6

값	0	0	2	4	6	6
인덱스	0	1	2	3	4	5

그리고 최종 인덱스 배열의 인덱스 4값을 하나 빼서 업데이트 시켜줍니다.

값	-1	1	1	2	2	3	3
인덱스	0	1	2	3	4	5	6

 

 

값	0	0	2	4	6	6
인덱스	0	1	2	3	4	5

그리고 최종 인덱스 배열의 인덱스 4값을 하나 빼서 업데이트 시켜줍니다.

그러면 0, 0, 2, 4, 6, 6으로 정렬할 수 있습니다.

 

시간 복잡도는 (n+α)입니다. 여기서 알파 값은 가장 큰 수 - 가장 작은 수 + 1 입니다.

그래서 가장 큰 수와 가장 작은 수의 차이가(배열의 범위가) 크다면 시간 복잡도가 크게 증가합니다.

그리고 stable한 정렬방식입니다.

def countSort(arr):
    length = len(arr)
    minNum = min(arr)
    maxNum = max(arr)

    #카운팅 배열 구하기
    alpha = maxNum - minNum + 1
    cntArr = [0]*alpha

    for i in arr:
        j = i - minNum
        cntArr[j]+=1

    #누적 카운팅 배열 구하기
    accArr = []
    accCnt=0
    for i in cntArr:
        accCnt+=i
        accArr.append(accCnt)

    #최종 인덱스 배열 구하기
    endIdxArr = [a-1 for a in accArr]

    #정렬 배열 구하기
    sortArr = [0]*length
    for i in reversed(arr):
        cntIdx = i - minNum
        endIdx = endIdxArr[cntIdx]
        sortArr[endIdx] = i
        endIdxArr[cntIdx]-=1

    return sortArr

파이썬 코드로는 이렇습니다.