[Algorithm] 계수 정렬

`이것이 코딩 테스트다 (나동빈)` 커리큘럼에 따라 진행합니다

 

✨ 계수 정렬

정의

- 매우 빠르게 동작하지만 특정한 조건이 부합할 때만 사용이 가능하다.

- 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능

- 데이터의 개수가 N, 데이터 (양수) 중 최댓값이 K일 때, 최악의 경우에도 수행 시간이 O(N+K)를 보장한다

동작 방식

1. 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성

    -> 정렬할 데이터의 가장 작은 데이터가 0이고, 가장 큰 데이터가 9이면, 0부터 9까지의 리스트를 생성한다

2. 데이터를 하나씩 돌면서 데이터와 동일한 인덱스에 데이터가 몇 번 등장했는지 개수를 센다.

시간 복잡도

- O(N+K)

- 때에 따라 심각한 비효율성을 초래할 수 있으니 주의해서 사용할 것

    -> ex) 데이터가 0과 9999로 단 두 개만 존재하는 경우

- 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용이 가능하다