[알고리즘] 특수한 상황에서의 빠른 정렬 - 계수, 기수 정렬

특정 상황에서 비교를 하지 않고 정렬을 함으로써 O(n) 시간 내에 정렬을 할 수 있다.

 

---

계수정렬(Counting Sort)

원소의 값이 한정적으로 0 ~ k의 자연수로 제한되어 있는 경우 사용 가능하다. 각 입력원소 x에 대해 x보다 작은 원소의 개수를 센다. 그리고 원소 x의 위치를 정한다. 예를 들어 x보다 작은 원소가 17개라면 x를 18번째 자리에 위치시킨다.

입력 배열 A와 출력을 저장할 배열 B, 임시 작업 공간 배열 C를 사용한다.

​

CountingSort(A, B, k){
  vector<int> C(k, 0);
  for j=1 to A.length
    C[A[j]]++;
    //C[i]는 값이 i인 원소의 개수이다.
  for j=1 to k
    C[j]+=C[j-1];
    //C[i]는 이제 값이 i보다 작거나 같은 원소의 개수이다.
    //따라서 C[A[j]]는 j보다 작거나 같은 원소의 개수이고 배열은 0부터 시작하므로
    //C[A[j]-1이 정렬된 배열에서 A[j]가 들어갈 위치이다.
  for j=A.length-1 down to 0{
    B[C[A[j]]-1] = A[j];
    //A[j]를 하나 배치했으므로, A[j]보다 같거나 작은 원소의 개수도 하나 줄어든다.
    C[A[j]]-;
  }
}

 

---

기수정렬(Radix Sort)

자릿수의 값 별로 정렬을 한다. 문자열, 정수를 빠른 시간내에 정렬할 수 있는 것은 장점이지만 부동 소수점은 정렬할 수 없는 것이 단점이다. 10진수라면 각 열은 10개의 버킷을 사용하여, 가장 낮은 자리부터 숫자를 차례대로 버킷에 담으면서 정렬한다.

​

예를 들어 [222, 96, 123, 1, 23, 5, 2, 17, 28]을 정렬하자.

 

1의 자릿수 기준으로 정렬

[1], [222, 2], [123, 23], [5], [96], [17], [28]

​

10의 자릿수 기준으로 정렬

[1, 2, 5], [17], [222, 123, 23, 28], [96]

​

100의 자릿수 기준으로 정렬

[1, 2, 5, 17, 23, 28, 96], [123], [222]

RadixSort(A){
  int max = A.getMax(); //배열A에서 최댓값을 얻는다.
  int res[A.size()]; //결과를 저장할 배열
  for(int exp = 1; max/exp>0; exp*=10)
    // 여기서의 countingSort는 일반적인 계수정렬은 아니고, 각 자리수별로 버킷에 저장하여 정렬하는 특수한 방식이다.
    countingSort(A, res, exp);
  }

countingSort(A, B, exp){
  int bucket[10] = {0, };
  for(int i=0; i<n; i++)
  //exp자릿수에 해당하는 count 증가
  bucket[(A[i]/exp) % 10]++;
  //일반적인 계수정렬을 위한 누적합 구하기
  for(int i=1; i<10; i++)
    bucket[i]+= bucket[i-1];
  for(i=A.size()-1 down to 0){
    B[bucket[(A[i]/exp) % 10] -1] = A[i]
    bucket[(arr[i]/exp) % 10]--;
  }
}

구현을 하면서 따라해보니 좀 헷갈렸는데, 그냥 정렬을 하는 게 아니라 (A[i]/exp)%10(A [i]/exp)%10이 A [i]의 exp자릿수라는 것을 기억하고 이를 기준으로 정렬한다고 생각하니 편했다. 계수정렬을 이용하는 이유는 계수 정렬은 k 이하의 수만 할 수 있는데 기수정렬은 자릿수의 정렬을 다루다 보니 9 이하의 정수를 정렬하는 것과 같아서 가장 효율적인 계수정렬을 이용한다.

​

기수정렬은 MSD와 LSD를 모두 이용할 수 있다. 큰 자릿수부터 정렬하는 MSD는 점진적으로 정렬을 완성해가므로 중간에 정렬이 완료될 수 있다는 장점이 있다. 하지만 MSD는 모든 데이터에 일괄적인 과정을 거치게 할 수 없다. 즉, 224, 232와 같이 두번째 단계에서 이미 결정되었지만 자리를 바꾸는 경우가 발생한다. 그렇기에 중간에 데이터를 점검해야 하고, 이 때문에 구현의 난이도가 LSD에 비해 높고 성능의 이점이 사라질 수 있다.