robustflame의 블로그

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 using namespace std; void countSort(char arr[], int range) { char newArr[strlen(arr)]; int cnt[range + 1] = { 0 }; for (int i = 0; arr[i];..