[알고리즘] 도수 정렬 ( = 카운팅 정렬 = 계수 정렬 )

도수 정렬은 요소의 대소관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘이다.

도수 정렬 알고리즘은 도수분포표 작성, 누적도수분포표 작성, 목적 배열 만들기, 배열 복사의 4 단계로 이루어집니다.

 

 

코드

 // 도수 정렬 함수(배열의 요솟값은 0 이상 max 이하)
 void fsort(int a[], int n, int max) {
     int i;
     int *f = calloc(max + 1, sizeof(int)); // 도수분포표 & 누적 도수
     int *b = calloc(n, sizeof(int)); // 작업용 목적 배열
     
     // step_0 (생략가능 : calloc함수가 동적으로 확보하는 메모리의 모든 값은 0으로 초기화되기 때문)
     for(i = 0; i <= max; i++) f[i] = 0;
     
     // step_1
     for(i = 0; i < n; i++) f[a[i]]++;
     
     // step_2
     for(i = 1; i <= max; i++) f[i] += f[i - 1];
     
     // step_3
     for(i = n - 1; i >= 0; i--) b[--f[a[i]]] = a[i];
     
     // step_4
     for(i = 0; i < n; i++) a[i] = b[i];
     
     free(b);
     free(f);
     
 }

 

각 for문 단계에서 배열 요소를 건너뛰지 않고 순서대로 스캔하기 때문에 같은 값에 대해서 순서가 바뀌는 일이 없어 이 정렬 알고리즘은 안정적이라고 할 수 있다. 

 

도수 정렬 알고리즘 시간복잡도 : O(n) 

 

 

도수 정렬 알고리즘 응용

 

요솟값의 범위가 min 이상 max 이하이고 요소의 개수가 n개인 배열 a를 도수 정렬하는 알고리즘

 

코드

// 도수 정렬 함수 (배열의 요솟값 범위는 min 이상 max 이하, 요소의 개수는 n개)
void fsort2(int a[], int n, int min, int max) {
    int i;
    int *f = calloc(max - min + 1, sizeof(int)); // + 1 인데, 배운 책에서는 + 2라고 잘못 나와있음.
    int *b = calloc(n, sizeof(int));
    
    // 추가된 제일 중요한 작업. 일단 min값으로 모두 빼줘. 기준값 생성. 나중에 다시 더해주면 돼
    for(i = 0; i < n; i++) {
        a[i] -= min;
    }
    
    //step_0(f의 요소 0으로 초기화해주는 작업) 생략. 어차피 calloc으로 할당받은 메모리는 모두 0으로 초기화되므로.
    for(i = 0; i < n; i++) f[a[i]]++; //
    for(i = 1; i <= max - min; i++) f[i] += f[i - 1];
    for(i = n - 1; i >=0; i--) b[--f[a[i]]] = a[i];
    for(i = 0; i < n; i++) a[i] = b[i];
    
    free(b);
    free(f);
    
    // 추가된 제일 중요한 작업. 빼줬던 min을 다시 더해줌.
    for(i = 0; i < n; i++) {
        a[i] += min;
    }

/*
배열 a의 증감( +-min)없이 아래 방법(f배열에서 증감처리하여 a에는 영향없게)도 있음
    for (i = 0; i < n; i++) f[a[i] - min]++;
    for (i = 1; i <= max - min; i++) f[i] += f[i - 1];
    for (i = n - 1; i >= 0; i--) b[--f[a[i] - min]] = a[i];
    for (i = 0; i < n; i++) a[i] = b[i];

*/
    
}