계수 정렬(Counting sort)

목차

1. 계수 정렬이란?
2. 사용 예시
3. 장점과 단점

1. 계수 정렬이란?

비교 없이 수행되는 정렬 알고리즘의 일종입니다.
원소들의 갯수를 세는 방법을 사용합니다.

2. 사용 예시

위 배열을 예시로 계수 정렬을 실행해보겠습니다.
정렬을 진행하기 위해서는 우선 counting array를 준비합니다.
counting array는 각 원소에 해당하는 갯수를 세기 위해서 사용하기 때문에 배열의 0부터 최댓값까지의 counting array를 준비해야합니다.
각 배열은 0으로 초기화합니다.

기존 배열을 차례대로 카운트해줍니다.


위 모습처럼 카운트 과정을 끝까지 수행하면 couting array는 다음과 같은 모습을 보입니다.

구해진 counting array를 이용해 누적 합을 구합니다.
다음을 표로 나타내면 다음과 같습니다.

원소 0의 누적 합이 1이라는 것은 1번까지 원소가 0이라는 뜻이며, 차례대로 원소 1의 누적 합은 3이기 때문에 2, 3번은 입니다. 이런 과정을 표로 나타내면 아래와 같습니다.

3. 장점과 단점

3-1. 장점

기본적인 경우 시간복잡도가 매우 낮습니다.
배열의 갯수를 N, 배열에 존재하는 가장 큰 수의 값을 K라고 할 때, 시간복잡도는 O(N + K)입니다.

3-2. 단점

배열이 1, 2, 2, 100으로 주어질 때 처럼 극단적인 경우 매우 비효율적인 알고리즘이 됩니다.
존재하지도 않는 3~99의 counting array를 순회해야 합니다.