Counting sort

지금까지 살펴본 알고리즘들은 원소들 간의 비교를 통해 정렬작업을 수행한다.

어떤 비교 정렬 알고리즘이라도 원소 n개를 정렬할 때, 최악의 경우 O(n log n)이상의 수행속도를 갖을 수 없다. 

 

그러나, counting sort는 비교 알고리즘이 아니기 때문에 O(n)에 수행이 가능하다. 

 

counting sort는 두 가지를 전제한다. 

    1) n개의 입력원소 모두가 0~k 사이의 정수이다. 

    2) k=O(n)이다. 즉 k가 n에 비해 압도적으로 크지 않다. 

 

counting sort는 각 입력원소 x에 대해 x보다 작은 원소의 갯수를 셈으로써, 출력배열에서 원소 x의 위치를 정해가며 정렬한다. 

 

counting_sort(ary,sorted_ary,k)
	//count를 위한 ary 초기화
    count_ary[0~k]
    for i=0 to k
        count_ary[i]=0

    for i=0 to ary.length
        count_ary[ary[i]]=count_ary[ary[i]]+1
    //이제 count_ary[i]=는 i와 같은 원소의 개수를 나타낸다.
    
    for i=1 to k
        count_ary[i]=count_ary[i]+count_ary[i-1]
    //count_ary[i]는 이제 값이 i보다 작거나 같은 원소의 개수를 나타낸다. 
    
    for i=A.length down to 1	//배열의 시작이 1이라고 가정한다
        sorted_ary[count_ary[ary[i]]]=ary[i]
        count_ary[ary[i]]=count_ary[ary[i]]-1

 

계수정령의 중요한 특징은 안정성을 갖는다는 것이다.

이는 출력 배열에서 값이 같은 숫자가 입력 배열에 있던 것과 같은 순서로 나타난다는 것을 뜻한다. 

즉, 두 숫자가 같을 때는 입력 배열에서 먼저 나타나는 것이 출력 배열에서도 먼저 나타난다. 

보통 안정성이라는 특성은 정렬되는 원소에 부속 데이터가 붙어 다닐 때 중요한 특성으로 간주된다.