[C] 분포수 세기 정렬 예제[C] 분포수 세기 정렬 예제

Posted at 2015.03.09 23:02 | Posted in C



facebook에 글올리기



[C] 분포수 세기 정렬 예제


분포수세기는 아주 간단한 알고리즘으로 같은 키가 많이 있는 배열에 한해 적용할 수 있는 정렬 알고리즘이다.

분포수세기는 특정 키 값이 출현하는 빈도를 저장하여 누적분포를 이용하여 간단하게 정렬하는 방법이다.


분포수세기 알고리즘은 안정성이 있다. 그러기 위해서 배열의 뒤에서부터 앞으로 값을 꺼내온다.


Colored By Color Scripter

#include <stdio.h>
#include <malloc.h>

void dist_count(int a[], int n, int m){
    int i;
    int *b, *count;

    b = (int*)malloc(sizeof(int)*n);
    count = (int*)malloc(sizeof(int)*(m + 1));

    for (i = 0; i <= m; i++){    // 배열 0으로 초기화
        count[i] = 0;
    }
    for (i = 0; i < n; i++){    // 빈도수 계산
        count[a[i]]++;
    }
    for (i = 2; i <= m; i++){    // 누적 분포 계산
        count[i] = count[i - 1] + count[i];
    }
    for (i = n - 1; i >= 0; i--){    // 뒤에서부터 읽어 b에 저장
        b[--count[a[i]]] = a[i];
    }
    for (i = 0; i < n; i++){
        a[i] = b[i];
    }
    free(b);
    free(count);
}


void main(void){

    int arr[] = { 1, 3, 2, 2, 3, 1, 3, 2, 4, 2, 4, 3, 1, 2, 1, 2, 5, 1, 5, 3 };

    dist_count(arr, 20, 5);

    for (int i = 0; i < 20; i++){
        printf("%d\t", arr[i]);
    }
    

    return 0;
}



분포수세기는 정렬 알고리즘이라고 하기에는 한정된 용도에서만 적합하다.

분포수세기는 속도가 약 2N번의 비교와 1번의 전체 복사가 있는 정도여서 속도가 빠르다.

하지만 키 값의 분포를 저장하는 count 배열과 작업 겨로가를 임시로 저장할 b 배열을 생성해야 하므로 메모리의 소모가 너무 크다.


모든 배열이 특정한 범위만을 가지는 것은 아니고 특정한 범위를 가진다고 하더라도 그 범위가 너무 크기 때문에 적용이 어려운 경우가 있다.


저작자 표시 비영리 변경 금지
신고

'C' 카테고리의 다른 글

[C] 퀵정렬 예제 정리  (0) 2015.03.14
[C] 분포수 세기 정렬 예제  (0) 2015.03.09
[C] 쉘정렬 사용 예제  (0) 2015.03.09
[C] 버블 정렬 예제 정리  (0) 2015.03.01
[C] 삽입 정렬 예제 정리  (0) 2015.02.24
[C] 선택정렬 SelectSort 코드  (0) 2015.02.23
이웃추가
facebook에 글올리기

Name __

Password __

Link (Your Website)

Comment

SECRET | 비밀글로 남기기