[알고리즘] Sorting in leanar time(선형시간 알고리즘)

Sorting in leanar time(선형시간 알고리즘)

앞서 보았던 예제를 제외한 정렬 알고리즘을 보자.

먼저 count 알고리즘이다.

count 알고리즘의 조건은 다음과 같다.

1) n개의 정수를 정렬하라(단, 모든정수는 0에서 n사이의 정수이다.)

예) n명의 학생들의 시험 점수를 정렬하라. 단 모든 점수는 100 이하의 양의 정수이다.

k이하의 정수라는 사전정보가 있고 이 정보를 이용하여 정렬하므로

comparison sort가 아니다.

count 알고리즘은 k 가 비교적 작을때 적용할 수있는 알고리즘이다.

따라서 k가 5일때 예를 들어 알아보도록 하자

이 때, C라는 배열은 카운터이다.

카운트 알고리즘은 입력 배열을 처음부터 끝까지 스캔하면서

그 값들이 각각 몇개가 있는지 카운트해서 C라는 배열에 저장해준다.

int A[n];
int C[k] = {0,};
for(int i=1; i<=n; i++)
    C[A[i]]++;
for(int s=1, i=0; i<=k; i++){
    for(int j=0; j<c[i]; j++){                                                                              
        A[s++] = j;
    }
}

우리가 생각할수 있는 간단한 방법으로 코드를 작성했다. 

그러나 실제 프로그램에서 저장되어있는 데이터들은 key값과 value값이 함께 있다.

그래서 보통 정렬 알고리즘을 설명하기 위해서 데이터가

정수형이나 실수형이라는 것을 가정했으나,

그것보다 더큰 단위의 데이터의 부분일 확률이 크다.

즉, 전화번호부 라는 데이터를 수정할경우

이름만 바뀌는 것이아니라 이름과 붙어 다니는 전화 번호까지 바뀌어야한다.

따라서 위와 같은 코드는 정렬된 key값만 옮기므로

좋은 코드가 아니라고 할수 있다.

따라서 같이 붙어다니는 데이터까지 이동해야 한다.

이를 위해서 약간 복잡한 과정을 거져야하는데

스텝 (a)에서 스텝 (b) 로 넘어갈 때 배열 C의 누적합을 구한다.

이 누적합이 가지고 있는 정보를 어떻게 해석할까

예를 들면 배열 A의 마지막 값은 3인데 

누적합 배열 C에서 인덱스 3이 7이라는것은 

3보다 작거나 같은것이 총 7개 라는것이다.

따라서 새로운 배열 B 인덱스 7번에 3을 넣어준다.

만약 또 3이 나온다면 이미 7번자리를 3이 차지했으므로

7번 바로 앞, 즉, 6번 자리에 3을 넣어준다.

이와 같은 분류작업을 반복하면 정렬이 완료된다.

Counting-Sort(A,B,k){
    for i<-0 to k
        do C[i] <-0
    for j<-1 to length[A]
        do C[A[j]]<-C[A[j]+1]
    // C[i] now contains the number of elements equal to i
    for i<-1 to k
        do C[i]<-C[i] + C[i-1]
    // C[i] now contains the number of elements less than or equal to i                                     
    for j<-length[A] downto 1
        do B[C[A[j]]] <- A[j]
            C[A[j]]<-C[A[j]]-1
}
 

이를 소스로 정리하면 다음과 같다.

첫번째 for 문은 카운트 배열 C를  0으로 초기화 하고

두번째 for 문은 카운트를 하며

세번째 for 문은 누적합을 구한다.

마지막으로, 누적합을 이용해서 배열 A를 마지막 부터 처음까지 살펴보면서

배열 B의 인덱스가 C[A[j]]가 되는 곳에 A[j]를 저장한다.

그리고 나서 그 값에 해당하는 카운트 값을 1 감소시켜준다.

이 알고리즘의 시간복잡도는 세타(n+k)이다.

단점은 k가 클수록 비효율적이라는 점이다.

그리고 count 정렬은 안정(stable) 정렬 알고리즘인데,

안정 정렬 알고리즘은 

"입력에 동일한 값이 있을 때 입력에 먼저 나오는 값이 출력에서도 먼저나온다"

라는 뜻이다.

출처 : 부경대 권오흠 교수님, 영리한 프로그래밍을 위한 알고리즘