[서울대학교 논자시 준비] 알고리즘 : chapter 4 정렬 - 계수정렬

앞서 설명한 정렬 알고리즘들의 공통점은 원소끼리 비교하는 것으로만 정렬을 한다는 것이다. 이런 정렬을 '비교정렬'이라고 한다. 이러한 비교정렬은 최악의 경우 수행 시간이 절대 O(nlogn)을 밑돌 수 없다. 

 

정렬하고자 하는 원소들이 특수한 성질을 만족하면 이 하한보다 더 빠른 정렬 알고리즘을 적용할 수 있다.

 

기수정렬

기수 정렬은 입력이 모두 k자릿수 이하의 자연수인 특수한 경우에 사용할 수 있는 방법으로 O(n)시간이 소요되는 정렬 알고리즘이다.

 

기수정렬은 우선 가장 낮은 자릿수만 가지고 모든 수를 정렬한다. 그런 다음 가장 낮은 자릿수는 잊어버린다. 그리고 앞과 같은 방법으로 더 이상 자릿수가 남지 않을 때까지 반복한다. 이렇게 하면 마지막에는 정렬된 배열을 갖게된다.

 

계수정렬

계수 정렬은 정렬하고자 하는 원소들의 값이 O(n)을 넘지 않는 경우에 사용할 수 있다. 예를들어, 배열 A[1 .. n]의 원소들이 k를 넘지 않는 자연수인 경우를 들 수 있다. 

 

계수 정렬은 먼저 배열의 원소를 훑어보고 1부터 k까지의 자연수가 각각 몇번 나타나는지를 센다. 이 정보가 있으면 A[1 .. n]의 원소가 몇번째에 놓이면 되는지를 계산할 수 있다. 

 

countingSort(A[], B[], n)
// A : 입력 배열, B : 정렬한 결과
{
for i<-1 to k 
	C[i]<-0;

for j<-1 to n
	C[A[j]]++;

for i<-2 to k
	C[i]<-C[i]+C[i-1];

for j<-n downto 1{
	B[C[A[j]]<-A[j];
    C[A[j]]--;
}
}

계수 정렬의 시간복잡도는 O(n)이다.