c언어계수정렬공간복잡도1 계수 정렬(카운팅 정렬) 개념, 분석, 활용 계수 정렬(카운팅 정렬)이란? 계수 정렬은 특정 범위에 있는 값을 정렬하는 정렬 기법입니다. 각 값의 개수를 셉니다. 계수 정렬은 복잡도가 굉장히 낮습니다. 시간 복잡도는 무려 O(n+k). (n: 나열된 요소 개수 e.g. 5개, k: 입력의 범위 [가장 큰 요소 - 가장 작은 요소]) 공간 복잡도도 무려 O(K)가 됩니다. 아주 빠른 배열임에도 불구하고 음수인 요소에 대해서는 정렬할 수 없다는 단점이 있습니다. 음수 인덱스는 없기 때문입니다. 계수 정렬 예시를 통한 이해 아래 예시로 한번에 이해하도록 해 보겠습니다. 1) 1 3 2 4 5 1 1를 나열해야 합니다. 2) 우리는 나열된 숫자의 범위가 1~5 안에 있다는 것을 알고 있습니다. 3) 배열을 선언합니다. int arr[5];로 선언합니다. .. 2022. 7. 2. 이전 1 다음