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

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

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

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

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

#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 배열을 생성해야 하므로 메모리의 소모가 너무 크다.

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

출처: https://hyeonstorage.tistory.com/360?category=622873 [개발이 하고 싶어요]