기수 정렬

기수 정렬

분류	정렬 알고리즘
자료 구조	배열
최악 시간복잡도	$O(w\cdot (k+n))$: 여기서 w는 기수의 크기, k는 기수의 도메인 크기
공간복잡도	$O(k+n)$: 여기서 k는 기수의 도메인 크기

기수 정렬(radix sort)은 기수 별로 비교 없이 수행하는 정렬 알고리즘이다. 기수로는 정수, 낱말, 천공카드 등 다양한 자료를 사용할 수 있으나 크기가 유한하고 사전순으로 정렬할 수 있어야 한다. 버킷 정렬의 일종으로 취급되기도 한다.

기수에 따라 원소를 버킷에 집어 넣기 때문에 비교 연산이 불필요하다. 유효숫자가 두 개 이상인 경우 모든 숫자 요소에 대해 수행될 때까지 각 자릿수에 대해 반복한다. 반복할 때마다 기수의 도메인 크기만큼의 누적합이 요구된다. 따라서 전체 시간 복잡도는 $O(w(n+k))$($w$는 기수의 크기, k는 기수의 도메인 크기)가 된다. 정수와 같은 자료의 정렬 속도가 매우 빠르다. 하지만, 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다. 기수 정렬은 정렬 방법의 특수성 때문에, 일부 특수한 비교 연산이 필요한 데이터에는 적용할 수 없을 수 있지만, 사용 가능할 때에는 매우 좋은 알고리즘이다.

역사

대량의 천공 카드를 기수 정렬하는 IBM 카드 분류기 . 카드는 작업자의 턱 아래에 있는 호퍼로 공급되고 카드의 한 칸에 천공으로 표현된 자료를 기반으로 기계에 딸린 13개의 배출 칸 가운데 하나로 분류된다. 입력 호퍼 근처의 크랭크는 정렬이 진행되며 판독 헤드를 다음 칸으로 이동시킨다. 뒷면의 랙에는 이전 정렬 단계의 카드가 들어 있다.

기수 정렬의 역사는 1887년 허먼 홀러리스가 작표기를 만들 때까지 거슬러 올라간다. 기수 정렬 알고리즘은 이미 1923년에 천공 카드를 분류하는 방법으로 널리 사용되었다.

Harold H. Seward은 1954년 매사추세츠 공과대학교에서 최초로 메모리 효율적인 컴퓨터 알고리즘을 개발했다. 이전까지는 알 수 없는 크기의 버킷을 가변 할당해야 한다고 믿었기 때문에 전산화 된 기수 정렬은 비현실적인 것으로 생각되었다. Seward의 혁신은 선형 탐색으로 사용하여 필요한 버킷 크기와 오프셋을 미리 결정하여 보조 메모리에서 단일 정적 할당만 할 수 있도록 하는 것이다. 이 선형 탐색은 Seward의 다른 알고리즘인 계수 정렬과 밀접한 관련이 있다.

현대에는 이진 문자열과 정수 정렬에 가장 널리 적용된다. 일부 벤치마크에서 다른 범용 정렬 알고리즘보다 50%에서 3배까지 빠를 때도 있는 것으로 나타났다.

자리 순서

기수 정렬은 최상위 유효숫자(MSD)나 최하위 유효숫자(LSD)에서 시작하도록 구현할 수 있다. 예를 들어 1234를 사용하면 하면 1(MSD) 또는 4(LSD)로 시작할 수 있다.

LSD 기수 정렬은 일반적으로 짧은 키가 긴 키보다 먼저 나오고 같은 길이의 키는 사전 순으로 정렬된다. 그 결과는 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] 와 같은 정수 표현의 일반적인 순서와 일치한다. LSD 정렬은 일반적으로 안정 정렬이다.

MSD 기수 정렬은 문자열이나 고정 길이 정수 표현 정렬에 적합하다. [b, c, e, d, f, g, ba]는 [b, ba, c, d, e, f, g] 로 정렬된다. 사전식 순서로 10진법의 가변 길이 정수를 정렬하면 1부터 10까지의 숫자는 [1, 10, 2, 3, 4, 5, 6, 7, 8, 9] 로 출력된다. 더 짧은 키는 왼쪽 정렬되고 오른쪽이 공백 문자로 채워지는 셈이다. MSD 정렬은 특정 구현 방식에서는 불안정 정렬이므로 중복 키의 원래 순서를 항상 유지하지는 않는다.

순회 순서 외에 MSD와 LSD 정렬은 가변 길이 입력 처리가 다르다. LSD 정렬은 길이별로 무리지어 각 무리를 기수정렬하고 길이 순서로 무리를 연결할 수 있다. MSD 정렬은 짧은 키를 가장 긴 키의 길이로 확장하고 정렬하는 효과를 가지기 때문에 LSD에서 무리를 구성하는 것보다 더 복잡할 수 있다.

하지만 MSD 정렬은 세분화 및 재귀에 더 적합하다. MSD 정렬의 각 단계에서 만들어진 버킷은 이전 단계에서 만든 다른 버킷을 참조하지 않고 그 안에서 다음 최상위 숫자를 사용하여 기수 정렬을 다시 적용할 수 있다. 마지막 숫자에 도달하면 모든 버킷을 연결하면 정렬이 완료된다.

복잡도와 성능

기수 정렬의 시간복잡도는 O(nw)이다. 여기서 n은 키의 수이고 w는 키의 길이이다. LSD는 위에서 설명한대로 가변 길이 키를 여러 무리로 분할하면 w에 대한 하한인 '평균 키 길이'를 달성할 수 있다.

적당한 도메인에서 최적화 된 기수 정렬은 매우 빠를 수 있다. 사전식 자료로 제한되기는 하지만 많은 응용에서는 제한이 없는 것이나 마찬가지다. 유도 시행 횟수가 병목이 될 정도로 키 크기가 크면 LSD 구현이 어려워 질 수 있다

예

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