정렬 알고리즘 3부 - 계수,기수,버킷 정렬

계수 정렬

계수 정렬은 입력키가 어떤 범위, 예를 들어 1부터 k 사이의 작은 정수 범위에 있다는 것을 알고 있을 때에만 적용할 수 있는 방법으로

어떤 입력 키 x의 정렬 위치는 x보다 작은 키가 몇 개나 입력에 나타나는지를 알면 결정할 수 있다. 예를 들어 입력키들이

숫자일 때 입력에 10이라는 키가 있고 이보다 작은 키가 5개 있다면 10 은 정렬 순서에서 여섯 번째에 위치한다. 계수 정렬에서는

입력키들이 범위 k 내의 각 값에 대하여 입력키가 실제로 입력에 나타나는 횟수를 계산한다.

#include <stdio.h>
#include <stdlib.h>
 
void printArray(int * array, int size){
 
  int curr;
  for(curr = 0; curr < size; curr++){
    printf("%d, ", array[curr]);
  }
  printf("\n");
}
 
int maximum(int * array, int size){
 
  int curr = 0;
  int max = 0;
 
  for(curr = 0; curr < size; curr++){
    if(array[curr] > max){ max = array[curr]; }
  }
 
  return max;
}
 
void countingSort(int * array, int size){
 
  int curr = 0;
  int max = maximum(array, size);
  int * counting_array = calloc(max, sizeof(int)); // Zeros out the array
 
  for(curr = 0; curr < size; curr ++){
    counting_array[array[curr]]++;
  }
 
  int num = 0;
  curr = 0;
 
  while(curr <= size){
    while(counting_array[num] > 0){
      array[curr] = num;
      counting_array[num]--;
      curr++;
      if(curr > size){ break; }
    }
    num++;
  }
  printArray(array, size);
}
 
int main(){
 
  int test1[] = {2, 6, 4, 3, 2, 3, 4, 6, 3, 4, 3, 5, 2, 6};
  int size1 = 14;
 
  countingSort(test1, size1);
 
  int test2[] = {5, 6, 7, 8, 5};
  int size2 = 5;
 
  countingSort(test2, size2);
 
  int test3[] = {8, 1, 2, 3, 3, 4};
  int size3 = 6;
 
  countingSort(test3, size3);
 
  return 0;
}

계수 정렬 알고리즘의 시간 복잡도는 O(n+k)로 보통 k = O(n)일 때에만 사용하므로 실질적으로 시간 복잡도가O(n)이다.

계수 정렬의 한 가지 중요한 성질은 동일한 키의 상대적 순서가 바뀌지 않는 안정적인 정렬이란 것이다..

기수 정렬

기수 정렬은 전체 키를 여러 자리로 나누어 각 자리마다 계수 정렬과 같은 안정적인 알고리즘을 적용하는 방법이다. 

d 자릿수 숫자들에 대하여 계수 정렬로 정렬한다면 각 자리에 대하여 O(n) 시간이 걸리므로 전체로는 O(dn) 시간이

걸리는데 d를 상수로 취급 할 수 있다면 결론적으로는 O(n)의 시간이 걸린다고 볼 수 있습니다. 기수 정렬은 각 자릿수를

정렬할 때 계수 정렬을 이용했는데 이 계수 정렬은 정렬 과정에서 전체 정렬 데이터 개수만큼의 메모리와 진법 크기만큼의

메모리가 추가로 필요한 비제자리 정렬입니다. 그로므로 메모리의 여유가 많지 않을 경우에는 실제로 적용하기

어려운 정렬 방법이라 볼 수 있쬬.

  /**
   * @data  정수 배열
   * @size  data의 정수들의 개수
   * @p  숫자의 최대 자리수
   * @k  기수(10진법을 사용한다면 10)

   */
  void rxSort(int *data, int size, int p, int k) {
    int *counts, // 특정 자리에서 숫자들의 카운트
        *temp; // 정렬된 배열을 담을 임시 장소
    int index, pval, i, j, n;
    // 메모리 할당
    if ( (counts = (int*) malloc(k * sizeof(int))) == NULL )
      return;
    if ( (temp = (int*) malloc(size * sizeof(int))) == NULL )
      return;
    for (n=0; n<p; n++) { // 1의 자리, 10의자리, 100의 자리 순으로 진행
      for (i=0; i<k; i++) 
        counts[i] = 0; // 초기화
       // 위치값 계산.
      // n:0 => 1,  1 => 10, 2 => 100
      pval = (int)pow((double)k, (double)n);
      // 각 숫자의 발생횟수를 센다.
      for (j=0; j<size; j++) {
        // 253이라는 숫자라면
        // n:0 => 3,  1 => 5, 2 => 2
        index = (int)(data[j] / pval) % k;
        counts[index] = counts[index] + 1;
      }
      // 카운트 누적합을 구한다. 계수정렬을 위해서.
      for (i=1; i<k; i++) {
        counts[i] = counts[i] + counts[i-1];
      }
      // 카운트를 사용해 각 항목의 위치를 결정한다.
      // 계수정렬 방식
      for (j=size-1; j>=0; j--) { // 뒤에서부터 시작
        index = (int)(data[j] / pval) % k;
        temp[counts[index] -1] = data[j];
        counts[index] = counts[index] - 1; // 해당 숫자 카운트를 1 감소
      }
      // 임시 데이터 복사
      memcpy(data, temp, size * sizeof(int));
    }
  }

기수 정렬은 정렬 방법의 특수성 때문에, 부동소수점 실수처럼 특수한 비교연산이 필요한 데이터에는 적용할 수 없지만, 사용 

가능할 때에는 매우 좋은 알고리즘입니다..

버킷 정렬

계수 정렬을 버킷 정렬로 부르는 경우도 있는데 여기서의 버킷 정렬은 계수 정렬을 일반화한 것으로 간주할 수 있습니다. 계수 정렬은

키값이 작은 안에 들어올 때 적용 할 수 있는 방법이지만 버킷 정렬은 키값의 범위뿐만이 아니라 그 범위 내에서 키값이 확률

적으로 균등하게 분포된다고 가정할 수 있을 떄 적용할 수 있는 방법입니다.