> For the complete documentation index, see [llms.txt](https://kukingclass.gitbook.io/computerscience/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kukingclass.gitbook.io/computerscience/algorithm/count-sort.md).

# 계수 정렬(Count Sort)

## 정의

**특정 조건이 부합할 때**는 매우 빠른 정렬 알고리즘입니다.

* 특정 조건이란?

  `데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때`에 사용할 수 있습니다.

  시간복잡도는 `O(N+K)`로, **K는 데이터 중 최댓값**입니다. 따라서 데이터의 크기가 제한되어 있다면 데이터 개수가 많더라도 빠르게 동작합니다.
* 범위 제한

  실수형 데이터인 경우 값이 **무한한 범위**를 가지므로 사용하기 어렵습니다.
* 적절한 크기 범위

  일반적으로 크기 범위가 1,000,000을 넘지 않을 때(가장 큰 데이터 - 가장 작은 데이터 차이가 백만을 넘지 않을때) 효율적으로 사용할 수 있습니다.

  * 왜 크기 범위가 제한되어 있어야 좋을까요?

    **모든 범위를 담을 수 있는 크기의 배열**이 필요하기 때문

    (예: max - min 차이가 A라면 A+1개의 크기의 배열이 필요함. A+1개의 숫자가 범위에 포함되어 있기 때문)

## 방법

```
입력 데이터: [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
```

먼저 MAX와 MIN의 범위가 모두 담길 수 있도록 배열을 생성합니다.

위 배열을 보면 가장 큰 데이터는 '9', 가장 작은 데이터는 '0'입니다.

그럼 0\~9를 모두 포함할 수 있도록 크기가 10인 배열을 선언해야 합니다.

그리고 입력 배열을 돌면서 카운팅을 합니다.

* 카운트한 배열

  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
  | - | - | - | - | - | - | - | - | - | - |
  | 2 | 2 | 2 | 1 | 1 | 2 | 1 | 1 | 1 | 2 |

그럼 카운트한 배열의 처음부터 돌면서 개수만큼 출력하면 정렬한 결과가 될 것입니다.

```
결과 데이터: [0, 0, 1, 1, 2, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9]
```

## 소스 코드

```python
# 입력 배열
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 카운팅위한 배열
count = [0] * (max(array) + 1) # 입력이 0 이상이라는 가정하에 최댓값까지 포함해서 카운팅 배열 선언
# 카운팅
for i in range(len(array)):
  count[array[i]] += 1
# 카운팅된 배열 작은 값부터 개수만큼 출력
for i in range(len(count)):
  for j in range(count[i]):
    print(i, end=' ')
```

## 복잡도

### 시간 복잡도

위 소스 코드를 보면, 계수 정렬의 시간복잡도는 O(N+K)입니다. 조건만 맞는다면 기수 정렬(Radix Sort)와 함께 가장 빠른 정렬이라고 할 수 있습니다. 단, 기수 정렬은 계수 정렬에 비해 처리할 수 있는 정수의 크기는 더 크고 좀 더 느립니다. (하지만 소스코드가 더 복잡해서 코딩테스트에서 반드시 기수 정렬을 이용해야만 해결할 수 있는 문제는 거의 출제되지 않는다고 합니다.)

### 공간 복잡도

* 데이터의 범위가 `1,000,000,000`이라면? 카운팅 배열을 int로 선언한다면, 4byte가 1,000,000,000개 필요합니다

  ∴ 4GB의 공간이 필요합니다. 따라서 사용할 수 없습니다.
* 예를 들어 입력 데이터가 \[0, 9, 0, 9, 0, 9, ....] 등 0과 9로만 이루어져있다고 합시다. 그러면 0과 9만 카운팅하면 되지만, 배열은 크기가 10으로 선언해야 합니다. 따라서 데이터에 따라 비효율적일 수가 있습니다.

그러므로 항상 쓸 순 없고, **범위가 제한되어 동일한 값을 가지는 데이터가 여러 개 등장할 때 효율적**입니다. 따라서 데이터 특성을 파악하기 어렵다면 퀵 정렬(대부분 정렬 라이브러리도 퀵 정렬과 비슷한 식으로 구현)이 가장 유리한 것입니다.

## 참고

* 이것이 취업을 위한 코딩테스트다 (나동빈)
* <https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html>