기수 정렬

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
IBM 카드 정렬기천공 카드 상에서 기수 정렬을 수행하고 있다.

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

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

[편집]

입력한 수열은 몇 개의 키로 분류된다. 예를 들어, 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));
    }
  }