/////
Search
Duplicate
📗

Counting Sort

작동 원리 : 원소의 범위가 0 ~ K 사이인 정수의 경우에만 사용가능. 배열의 크기와 K가 같으면 엄청난 효율을 보여준다. (최적 시간복잡도 O(n))
시간복잡도 : O(n2n^2)
Required Function : calloc
// 10개는 정렬되는데 이후 데이터부터는 에러남.. 이유가 몰까용??
찾아볼게여 ㅎㅎ..

C++, C

int *counting_sort(int *arr, int length, int maxnum) { int i; int *arr_result = (int *)calloc(length, sizeof(int)); int *arr_counting = (int *)calloc(maxnum, sizeof(int)); for (i = 0 ; i < length ; i++) arr_counting[arr[i]]++; for (i = 1 ; i < maxnum ; i++) arr_counting[i] += arr_counting[i - 1]; for (i = length - 1 ; i >= 0 ; i--) arr_result[--arr_counting[arr[i]]] = arr[i]; return (arr_result); }
C
복사