작동 원리 : 원소의 범위가 0 ~ K 사이인 정수의 경우에만 사용가능. 배열의 크기와 K가 같으면 엄청난 효율을 보여준다. (최적 시간복잡도 O(n))
시간복잡도 : O()
•
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
복사