[알고리즘 소개] Pair의 Counting Sort

Counting Sort는 특정 문제에서 굉장히 강력한 성능을 내는데, 앞서 얘기한 suffix array에서의 정렬 또한 counting sort를 이용하여 logN이라는 귀중한 시간복잡도를 나눌 수 있다!

일반적인 counting sort는 굉장히 쉬운 반면에, pair로 되어있으면 순간 뇌정지가 온다(필자는 Radix Sort를 놀랍게도 한번도 써보지 않았다!) 하지만, 조금의 요령만 있다면 counting sort를 두 번 하는 것으로 해결된다.

 

Remind – Stable Counting Sort

필자는 Counting Sort만 알고 Stable Counting Sort의 원리를 알지 못했어서 Pair의 Counting Sort를 이해하는데 어려움을 겪었었다. “Stable” Counting Sort에 대해 다시 명확히 살펴보고 가자.

 

int arr[MAX_N], count[MAX_SCOPE+1], ans[MAX_N];

arr := 정렬할 data가 들어있는 배열, 값들의 범위는 0~MAX_SCOPE

count[i] := 0~i까지 값이 arr에 몇 개 들어가있는지(누적합)

ans := arr가 정렬된 값이 들어갈 배열

int i, N; for (i=1;i<=N;i++) count[arr[i]]++; for (i=1;i<=MAX_SCOPE;i++) count[i]+=count[i-1]; for (i=N;i>=1;i--) ans[count[arr[i]]--] = arr[i];

 

여기서 핵심이라고 할 수 있는 줄은 마지막 줄이다.

arr[13] = {0, 1,2,3,3,2,1,1,2,3,1,2,3}; 이라고 했을 때

count는 다음과 같이 저장된다.

i	0	1	2	3
count[i]	0	4	8	12

i가 N(12)부터 1까지 1씩 감소하면서 ans에 다음과 같이 저장된다.

i	1	2	3	4	5	6	7	8	9	10	11	12
arr[i]	1	2	3	3	2	1	1	2	3	1	2	3

arr[i]	1	2	3
count[i]	4 => 0	8 => 4	12 => 8
ans log	i=10 ans[count[arr[10]]] = arr[10] (ans[4]=1) count[1]-- (count[1] = 4->3) i=7 ans[count[arr[7]]] = arr[7] (ans[3]=1) count[1]-- (count[1] = 3->2) i=6 ans[count[arr[6]]] = arr[6] (ans[2]=1) count[1]-- (count[1] = 2->1) i=1 ans[count[arr[1]]] = arr[1] (ans[1]=1) count[1]-- (count[1] = 1->0)	i=11 ans[count[arr[11]]] = arr[11] (ans[8]=2) count[2]-- (count[2] = 8->7) i=8 ans[count[arr[8]]] = arr[8] (ans[7]=2) count[2]-- (count[2] = 7->6) i=5 ans[count[arr[5]]] = arr[5] (ans[6]=2) count[2]-- (count[2] = 6->5) i=2 ans[count[arr[2]]] = arr[2] (ans[5]=2) count[2]-- (count[2] = 5->4)	i=12 ans[count[arr[12]]] = arr[12] (ans[12]=3) count[3]-- (count[3] = 12->11) i=9 ans[count[arr[8]]] = arr[8] (ans[11]=3) count[3]-- (count[3] = 11->10) i=4 ans[count[arr[4]]] = arr[4] (ans[10]=3) count[3]-- (count[3] = 10->9) i=3 ans[count[arr[3]]] = arr[3] (ans[9]=3) count[3]-- (count[3] = 9->8)

핵심은 arr[i]를 count[arr[i]]를 매개체로 저장을 하며, i가 내려갈 때 count[arr[i]]도 내려가기 때문에 결과적으로 같은 값에 대해서 stable하게 정렬할 수 있음을 보여준다.

 

- Overview

우리는 다음과 같은 배열을 선언해준다.

 

pair<int, int> arr[MAX_N]; // value scope : 0~MAX_SCOPE

int count[MAX_SCOPE+1]; // count[i] := 0~i까지의 value가 몇 번 나왔는지 count
int SOI[MAX_N]; // SOI[i] := second를 기준으로 정렬한 경우의 second의 값이 원래 배열에서 몇 번째에 있는지(value가 아닌 Index). Second value Order Index의 약자
pair<int, int> sorted_arr[MAX_N]; // sorted_arr := arr을 stable sort한 것

 

위와 같이 선언하였다면, 대략적인 알고리즘 순서는 다음과 같다.

[1] arr의 second값을 이용하여 counting sort, 그리고 SOI를 구한다.

[2] arr의 first값을 이용하여 counting sort 과정을 진행하여 count배열을 완성

[3] [1]에서 구한 SOI 값 역순으로 sorted_arr에 값 저장

 

소스코드를 보자.

int i, N; for (i=1;i<=N;i++) count[arr[i].second]++; for (i=1;i<=MAX_SCOPE;i++) count[i]+=count[i-1]; for (i=N;i>=1;i--) SOI[count[arr[i].second]--] = i; // SOI[--count[arr[i].second]]로 되어있는 경우는 i=0부터일 때이다 memset(count, 0, sizoef(count)); for (i=1;i<=N;i++) count[arr[i].first]++; for (i=1;i<=MAX_SCOPE;i++) count[i]+=count[i-1]; for (i=N;i>=1;i--) ans[count[arr[SOI[i]].first]--] = arr[SOI[i]];

 

이를 조금 더 확장시킨 것이 Radix Sort인데, 다음에 한번 다루어보도록 하겠다.