계수 정렬(counting sort)

계수 정렬(counting sort)는 키가 일정한 범위, 예를 들어, 1부터 M 사이의 정수로만 이뤄져 있다는 사실을 알고 있을 떄 사용할 수 있는 방법이다.

예를 들어 M = 4 이고 a = [1,2,2,1,3,4,4,1] 일 때 count 라는 배열을 만들어서 각 원소의 개수를 저장한다.

j	1	2	3	4
count[j]	3	2	1	2

그리고 이를 누적시켜서 저장한다.

j	1	2	3	4
count[j]	3	5	6	8

다음으로 배열 a에서 원소들을 뒤에서부터 하나씩 가져와서 count 리스트에 있는 인덱스에 따라 빈 배열 b로 복사한다. a에서 b로 복사하고 나면 count에 있는 인덱스 값을 하나 감소시킨다.

마지막으로 배열 b에 있는 원소들을 배열 a로 복사한다.

이러한 process 의 ADL은 다음과 같다,.

countingSort(a[],n,m)
	for (j <- 1; j <= m; j <- j+1) do count[j] <- 0;
    // count 배열 0으로 초기화
    for (i <- 1; i <= n; i <- i+1) do count[a[i]] <- count[a[i]] + 1;
    // 원소의 개수를 세어 count[]에 저장
    for (j <- 2; j <= m; j <- j+1) do count[j] <- count[j-1] + count[j];
    // 원소가 들어갈 위치 계산
    for (i <- N; i >= 1; i <- i-1) do {
    	b[count[a[i]]] <- a[i]; // a의 원소를 b의 미리 계산된 위치로 이동
        count[a[i]] <- count[a[i]]-1; // count의 값 하나 감소시킴
    }
    for (i <- 1; i <= n; i <- i+1) do a[i] <- b[i]; // b를 a로 이동
end countingSort()

수행과정은 다음과 같다. [1,2,2,1,3,4,4,1] 에 대한 수행과정이다.

countingsort

첫번째는 가장 작은 원소를 먼저 자리잡게 한다. b[count[min(a)]] = min(a) 라고 생각하면 된다.

누적개수에서 하나씩 빼서 빈 행렬 b를 채워나간다. 그리고 count에서 뺀 수가 전 수의 개수와 같으면 숫자를 바꿔주고 채워나간다. 

countingSort는 안정적이고 시간복잡도는 \( O(N) \) 이고, 추가 기억장소가 필요하기 때문에 제자리 정렬은 아니다.

pythoh 코드는 다음과 같다.

def countingSort(a,n,m): # n = len(a), m = a 원소의 최대값
    b = [0]*(n+1)
    count = [0] * (m+1)
    for j in range(1,m+1):
        count[j] = 0

    for i in range(1,n+1):
        count[a[i]] += 1

    for j in range(2,m+1):
        count[j] += count[j-1]

    for i in range(n,0,-1):
        b[count[a[i]]] = a[i]
        count[a[i]] -= 1

    for i in range(1,n+1):
        a[i] = b[i]

    return a

a = [-1,1,2,2,1,3,4,4,1]
print(countingSort(a,len(a)-1,max(a)))