기수 정렬

기수 정렬(radix sort)은 큰 자리수부터 비교하여 정렬해 간다는 것이 기본 개념으로 하는 정렬 알고리즘이다. 자릿수가 고정되어 있으니, 안정성이 있고(이때 데이터들 간의 상대적 순서는 보존되어야 한다.) 시간 복잡도는 $O(dn)$이다.($d$는 가장 큰 데이터의 자리수)

기수 정렬은 비교 연산을 하지 않으며, 무엇보다도 전체 시간 복잡도 역시 $O(dn)$이어서, 정수와 같은 자료의 정렬 속도가 매우 빠르다. 하지만, 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다. 기수 정렬은 정렬 방법의 특수성 때문에, 부동소수점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없지만, 사용 가능할 때에는 매우 좋은 알고리즘이다.

예

입력한 수열은 몇 개의 키로 분류된다. 예를 들어, 3자리이하 수라면, 1의 자리, 10의 자리, 100의 자리로 나누어 분류된다. 각각의 키에 대해 하위 키부터 정렬한다.

예를 들면,

170, 45, 75, 90, 2, 24, 802, 66

와 같이 데이터가 주어졌을 때, 수열의 1의 자리만 보고 정렬을 수행하면,

170, 90, 2, 802, 24, 45, 75, 66

이 된다. 이 수열을 가지고 다시 10의 자리에 대해 정렬을 하면,

2, 802, 24, 45, 66, 170, 75, 90

가 된다. 마지막으로 100의 자리에 대해 정렬을 하면,

2, 24, 45, 66, 75, 90, 170, 802

이 되어 정렬이 완료된다.

소스 코드

C

  /**
   * @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));
    }
  }