Counting Sort, Radix Sort

Counting Sort

---

계수 정렬(Counting Sort)은 총 \(n\)개의 원소가 1에서 \(k\)의 범위에 있을 때, 선형 시간복잡도 \(O(n+k)\)를 가지는 빠른 정렬 방법이다. \(O(nlog_2n)\)의 시간복잡도를 가지는 Merge Sort, Heap Sort, Quick-Sort 같은 정렬법보다도 빠르게 동작한다. 단, 원소의 범위가 1에서 \(n^2\)이라면 \(O(n^2)\)의 시간복잡도를 가지게 되는 제약이 있다.

구현

#include <bits/stdc++.h> using namespace std; void countSort(char arr[], int range) { char newArr[strlen(arr)]; int cnt[range + 1] = { 0 }; for (int i = 0; arr[i]; i++) ++cnt[arr[i]]; for (int i = 1; i <= range; i++) cnt[i] += cnt[i - 1]; for (int i = 0; arr[i]; i++) { newArr[cnt[arr[i]] - 1] = arr[i]; --cnt[arr[i]]; } for (int i = 0; arr[i]; i++) arr[i] = newArr[i]; } int main() { char arr[] = "HELLOWORLD"; int range = (int) numeric_limits<char>::max(); cout << "Before Sorting: " << arr << endl; // HELLOWORLD countSort(arr, range); cout << "After Sorting: " << arr << endl; // DEHLLLOORW }

Radix Sort

---

기수 정렬(Radix Sort) 또는 버킷 정렬(Bucket Sort)라고도 불리는 이 정렬 방법은 앞서 본 계수 정렬(counting sort)이 가졌던 원소 범위의 한계를 어느 정도 극복할 수 있는 정렬법으로 선형 시간 정렬을 가능케 한다. 간단하게 설명하기 위해 아래와 같은 정수 배열이 있다고 해보자.

45, 7, 16, 12, 611, 317

위 배열에서 일의 자리수를 정렬의 키로 사용하여 계수 정렬(counting sort)하면 다음과 같이 된다.

611, 12, 45, 16, 7, 317

그 다음에 십의 자리, 백의 자리로 차례로 정렬을 거치고 나면 모든 원소들이 오름차순으로 정렬된다.

7, 611, 12, 16, 317, 45 

7, 12, 16, 45, 317, 611

기수 정렬의 시간복잡도는 \(O(d \times (n + b))\)인데 여기서 \(b\)는 한 자릿수의 범위로 8진법에서는 8, 10진법에서는 10, 16진법에서는 16이다. 그리고 \(d\)는 원소들 중 가장 큰 원소의 자릿수를 의미하는데 19는 두 자릿수, 8736는 네 자릿수이다. 그리고 원소들 중 가장 큰 원소를 \(k\)라고 했을 때, \(d = O(log_bk)\)이므로 원하는 환경의 공간복잡도와 시간복잡도를 잘 고려하여 \(b\)와 \(d\)를 적절히 조정하는 것이 중요하다.

※ 정렬 알고리즘의 속성 중 안정성(stability)이라는 것이 있다. 여기서 말하는 안정성은 정렬시 같은 내용을 가지는 키값의 배열이 정렬 후에도 상대적 순서가 그대로 유지되는 속성이다. 기수 정렬은 여러 개의 키에 우선순위를 정해서 정렬하는 알고리즘으로 각 키로 정렬할 때마다 안정성이 보장되어야 하는데, 계수 정렬(counting sort)은 이러한 안정성이 보장되는 정렬 방법으로 기수 정렬에서 서브 정렬법으로 사용한다.

구현

#include <bits/stdc++.h> using namespace std; const int RANGE = 10; void countingSort(int arr[], int n, int e) { int newArr[n]; int count[RANGE] = { 0 }; for (int i = 0; i < n; i++) { ++count[(arr[i] / e) % RANGE]; } for (int i = 1; i < RANGE; i++) count[i] += count[i - 1]; for (int i = n - 1; i >= 0; i--) newArr[--count[(arr[i] / e) % RANGE]] = arr[i]; for (int i = 0; i < n; i++) arr[i] = newArr[i]; } void radixSort(int arr[], int n) { int mv = 0; for (int i = 0; i < n; i++) mv = max(mv, arr[i]); for (int e = 1; mv / e > 0; e *= 10) countingSort(arr, n, e); } void print(int arr[], int n) { for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; } int main() { int arr[] = { 45, 7, 16, 12, 611, 317 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "Before Soring:" << endl; print(arr, n); radixSort(arr, n); cout << "After Sorting:" << endl; print(arr, n); return 0; }

참고 자료

• C로 배우는 알고리즘, 이재규
  
• http://www.geeksforgeeks.org/counting-sort/
• http://www.geeksforgeeks.org/radix-sort/