[C] Countsort:: 계수정렬

안녕하세요. 우주신 입니다.

이번 포스팅에서는 계수정렬(Count Sort)에 대해 알아보겠습니다.

앞선 포스팅에서의 삽입, 퀵, 힙 정렬 등의 방법은 정렬할 때 두 값을 비교하며 정렬을 했다.

이를 Comparison Sort라고도 부르는데, 이와 반대로 계수정렬은 비교를 하지 않고 정렬을 하기 때문에 

Non-Comparison Sort의 방법 중 하나이다.

[4 1 3 4 3] 리스트를 정렬하면서 자세히 알아보자.

우선, 두 개의 리스트 B, C를 만들어준다. 

B는 A 리스트를 정렬하여 결과물을 넣어줄 리스트이다.

C(Counting List)의 Index는 곧 A의 요소이고, C의 값은 A의 요소들의 갯수이다.

예를 들어 A에 4가 총 몇 개 나온지는 C의 4번째 Index를 보면 알 수 있다. 

그러므로, C 리스트의 길이는 A 리스트의 값들 중 가장 큰 값이 될 것 이다.

처음에는 C를 0으로 다 초기화 해준다.

이제 A의 첫번째 요소부터 Count하며 C를 업데이트 해준다.

A의 첫번째 요소는 4이므로 C의 4번째 칸에 1을 증가 시켜준다.

A의 다음 요소는 1이므로 C의 1번째 칸에 1을 증가 시켜준다.

.

.

.

이런식으로 A의 마지막 요소까지 순회하며 C를 업데이트하면,

1이 총 1번 나왔고, 2는 0번, 3은 2번, 4는 2번 나온 것을 알 수 있다.

아직 C는 완성되지 않았다. Counting 한 C의 각 값들을 직전 값을 더해 업데이트 해야 한다. 

C의 2번째 칸은 기존 값 0과 1번째 칸의 1을 더한 1이 된다.

마찬가지로, C의 3번째 칸은 기존 값 2에서 2번째 칸의 1을 더한 3이 된다.

C의 4번째 칸은 기존 값 2에서 3번째 칸의 3을 더한 5가 된다.

드디어 C 리스트가 완성이 되었다.

이제 이 C를 가지고 정렬 해보자.

A의 역순으로 훑으며 정렬을 한다.

A의 5번째 칸은 3이 들어있고, C의 3번째 칸으로 가면 3이 있다.

C의 3번째 칸의 3이 A의 5번째 칸의 3이 위치해야할 인덱스 값이다. 

즉, 3은 B 리스트의 3번째 자리에 위치한다. 그리고 위 그림처럼 C의 3번째 값을 1 감소 시킨다.

이번에는 A의 4번째 칸의 요소를 정렬 해야 한다.

4가 들어가 있다. C의 4번째 칸을 보면 5가 있었을 것이고 (위 그림은 1 감소 시킨 그림이다)

B의 5번째 인덱스에 4를 위치 시켜준다. 마찬가지로 C의 4번째 칸의 값을 1 감소 시킨다.

A의 3번째 칸의 요소를 정렬 한다. C의 3번째 칸으로 가면 2가 있었을 것이고

B의 2번째 인덱스에 3을 위치 시키고 C의 3번째 칸의 값을 1 감소 시킨다. 

반복해서, 2번째 값을 정렬 시키고

마지막으로 첫번째 값을 정렬 시키면 정렬이 완성 되었다.

이제 코드를 보며 한번 더 복습해보자. 

여기서  A = arr  //  B = sorted_arr  //  C = count_arr 이다

03:: 정렬되지 않은 리스트 A와 A의 size를 인자로 받는다

05:: 정렬된 결과를 받을 리스트 B를 생성 한다

07:: 리스트 A의 최대값을 찾는다

14:: 리스트 A의 최대값의 크기만큼 리스트 C를 생성 하고 0으로 모두 초기화 한다

20:: A를 돌면서 A 요소의 빈도수 만큼 C의 해당 인덱스에 채워넣는다

26:: C를 업데이트 한다

32:: A를 역순으로 훑으며 C를 참고하여 정렬한다

38:: 정렬된 리스트 B를 A에 복사 했다. (선택사항)

왜 Counting Sort이고, Non-Comparison 방식인지 이해 했을 것이다.

정렬되지 않은 리스트의 값들을 Count한 후에, 이 Count된 결과를 가지고 정렬을 하기 때문에 비교가 필요 없다.

Count Sort의 시간복잡도는 O(n + k)이다.

데이터가 n일 때, A를 Count하며 C에 갯수를 업데이트 하는 데 O(n)이 걸린다.

C를 가지고 A를 역순으로 훑으며 B를 만들 때도 O(n)이 걸린다.

k는 A 리스트 중 가장 큰 값을 가리킨다. 

업데이트 된 C를 바탕으로 직전 요소 값을 현재 요소 값에 더하는 데 k번 만큼 반복해야 하며 이는 O(k)가 걸린다.

그래서 만약 A의 최대값이 매우 큰 값이라면 Count Sort는 비효율적인 알고리즘인 것을 알 수 있다.

수고하셨습니다.

끝

# 참고 # 

 - "Introduction to Algorithm" Cormen, Charles, Ronald, Clifford

- 한양대학교, 정형수 교수님, 알고리즘 수업