계수 정렬 (Counting sort)

계수정렬

- 범위조건이 있는 데이터에 대하여 매우 빠른 속도를 갖는 알고리즘

- 크기를 기준으로 계수를 세면 되기 때문에 위치를 바꾸거나 할 필요가 없다.

- 순차적으로 맨 앞의 데이터부터 읽어들이면 되므로 O(n)의 시간 복잡도 가능

- 데이터(값)은 양수여야 한다.

- 값의 범위가 너무 크지 않아야 한다.(메모리 사이즈를 넘어서는 안된다)

- stable sort

- not-in-place algorithm

 

1. 정렬되어 있지 않은 배열의 수들이 몇번 나왔는 지 count배열에 적어놓는다.

2. 나온 수 만큼 수를 배열 해주면 된다.

 

 

- 원소들의 비교연산을 하지 않으므로, 비교 기반 알고리즘에 비해 빠르다.

- 입력 배열의 범위가 제한적이고 배열의 크기가 작은 경우에 효과적이다.

- 입력 배열의 범위가 큰 경우, 메모리 사용량이 많아질 수 있다.

- 입력 배열의 범위가 작은 경우나 값들이 밀집되어 있는 경우에 효과적인 알고리즘이지만, 범위가 크거나 값들이 희소한 경우에는 다른 알고리즘을 고려해야 한다.