[알고리즘] 계수 정렬 - 신기하게 잘 찾아들어간다!

계수정렬(Counting Sort)

각 항목이 몇개씩 있는지 세는 작업을 하면서 선형시간에 정렬

 

한계

정수나 정수로 표현할 수 있는것만 정렬가능

 

방법

최대값까지 배열 생성

입력원소의 발생 횟수를 세어 저장

 

예시

입력 배열: [0] [5] [4] [4] [1] [3] [2] [5] [1] [4] [6]

 

입력 원소의 최대값까지 카운트(Count) 배열 생성

위의 예에서는 0~6까지 정수, 7개를 가진 카운트 배열이 생성된다.

 

1. 카운트 배열 7개 각 원소의 발생 횟수를 세어 저장

0 원소의 개수 한번, 1이 두번, 2가 한번 등 6까지

그럼 카운트 배열은 이렇다

[1] [2] [1] [1] [3] [2] [1]

 

2. 카운트 배열의 값을 누적하여 저장

다시 카운트 배열의 값을 누적해서 만들어준다

[1] [2] [1] [1] [3] [2] [1]

 

앞의 값을 더해주며 만든다

[1] [3] [4] [5] [8] [10] [11]

 

마지막 11은 입력 원소의 개수와 같다

 

3. 입력자료 값에 해당하는 카운트 배열의 값을 얻고,

값에 해당하는 결과 배열의 위치에 입력자로의 값을 할당한다

 

4. 해당하는 카운트 배열의 값을 1만큼 감소시킨다

 

적용해보자!!

입력 자료: [0] [5] [4] [4] [1] [3] [2] [5] [1] [4] [6]

카운트 배열: [1] [3] [4] [5] [8] [10] [11]

 

입력자료의 첫번째 즉 0, 카운트 배열 0번째(1) 1의 자리에 0을 집어넣는다

 

[0] [] [] [] [] [] [] [] [] [] []

 

그리고 카운트 배열의 1을 감소 시킨다

카운트 배열은 이렇게 보인다

0, 3, 4, 5, 8, 10, 11

 

다음 입력 원소 5

카운트 배열의 5번째는 10이다

그럼 5를 10번째에 집어넣는다

결과 배열: [0] [] [] [] [] [] [] [] [] [5] []

 

그리고 카운트 배열 10에서 1을 감소시킨다

카운트 배열: [0] [3] [4] [5] [8] [9] [11]

 

다음 원소 4

카운트 배열의 4번째 8

8번째 자리에 4를 넣어준다

결과 배열: [0] [] [] [] [] [] [] [4] [] [5] []

그리고 카운트 배열에 1을 감소시킨다

카운트 배열: [0] [3] [4] [5] [7] [9] [11]

 

하나만 더 해보자

편의를 위해 입력 자료를 가져오고

입력 자료: [0] [5] [4] [4] [1] [3] [2] [5] [1] [4] [6]

 

다음 원소도 4

카운트 배열의 4번째는 전에 7로 바뀐녀석이다

그럼 7번째 4를 넣어준다

결과 배열: [0] [] [] [] [] [] [4] [4] [] [5] []

 

이렇게 반복을 해준다

 

실제 파이썬에서 구현해보면 이렇다

def counting_sort(A, B):
    k = max(A)
    C = [0] * (k + 1)
    print('init: ', C)
    for j in A:
        C[j] += 1;
    print('done : ', C)
    for i in range(1, len(C)):
        C[i] = C[i] + C[i-1];
    print('accum : ', C)
    for j in A:
        B[C[j]-1] = j;
        C[j] -= 1;
    return B

if __name__ == '__main__':
    A = [5, 4, 3, 2, 1, 0, 5, 4, 7, 15]
    B = [0]*len(A)
    result = counting_sort(A, B)
    print(result)