[정렬] 8. 한 살도 이해하는 계수 정렬(Counting Sort)

계수 정렬

: 주어진 배열의 값의 범위가 작은 경우 빠른 속도를 갖는 정렬 알고리즘이다.

  최댓값과 입력 배열의 원소 값 개수를 누적합으로 구성한 배열로 정렬을 수행한다.

 

우선, 이해하기 쉽게 

nums = [5, 9, 3, 6, 9, 5, 2, 10, 1] 이라는 배열이 입력되었고, 이 nums 배열을 정렬한다고 해보자.

 

카운팅 정렬의 단계

0. 정렬할 nums 배열 입력

 

1. count 배열 생성

- 입력된 nums 배열의 최댓값을 길이로 갖는 count 배열을 생성한다.

- 각 원소가 nums 배열에 몇 번 나오는지 횟수를 count 배열에 기록한다.

2. 이전까지의 누적개수를 기록하는 배열 생성(cumCount 배열)

- count 배열에서 각 원소가 몇 개씩 나오는지 알 수 있으므로,

- 이를 이용해 지금까지 몇개의 원소가 앞에 나왔는지를 기록하는 누적개수 배열을 생성한다.

3. nums 배열에서 첫번째 원소부터 cumCount 배열에 기록되어 있는 값에 따라 인덱스 위치를 정하면 끝!

 

시간 복잡도

:

만약 최대값이 주어지지 않은 경우, 전체 배열을 탐색해야 하므로 O(n) 소요,

Count 배열 생성하면서 갯수를 세는 과정 O(n) 소요,

누적 배열을 생성하면서 누적 갯수를 세는 과정 O(n) 소요

마지막으로 answer에 배열에 값을 입력하는 과정 O(n) 소요

 

따라서 시간 복잡도는 O(n)이 된다.

하지만, 배열의 길이와는 독립적으로 배열의 최댓값을 M이라고 한다면, 정렬 시간은 M을 따라가게 될 것이다.

따라서 O(n + M) 이라고 보는 것이 정확해 보인다.

 

과정에서 알 수 있듯이 최댓값이 작으면 작을수록 정렬에 유리하다.