카운팅 정렬(Counting Sort)

카운팅 정렬이란?

카운팅정렬은 값을 비교해서 정렬하는 방식이라기 보다는 값의 갯수를 세고 그 갯수에 따라서 위치를 성정하는 방식이다.

 

동작 원리는 다음과 같다.

 

3,2,2,3,1 와 같은 Array(배열)가 있을때

3

2

2

3

1

 

1. 각 데이터의 갯수를 모두 카운트 해준다.

 

- 위의 경우 Count[3] = 2; Count[2] = 2; Count[1] = 1가 된다.

 

2. 누적합을 계산하는 방식으로 1부터 최대값까지 누적 합하여 계산을 해준다.

 

- 예를 들면 Count[1] = Count[1] + Count[0] = 1

 

Count[2] = Count[2] + Count[1] = 2 + 1 = 3

 

Count[3] = Count[3] + Count[2] = 2 + 3 = 5

 

따라서 Count[1] = 1

 

Count[2] = 3

 

Count[3] = 5

 

3. 새로운 배열을 선언하고 누적합의 개수를 --연산 해준 후에 대입해준다.

 

위에서 우리는 Count[1] =1, Count[2] = 3, Count[3] = 5 각 카운트의 값을 얻었다.

 

배열에서는 인덱스가 0부터 시작이므로 들어 갈 수 있는 인덱스를 표현 할때는 1씩 빼줘서 표현한다.

따라서

3

2

2

3

1

3,2,2,3,1 배열에서 생기는 새 배열은 1부터 카운트 하면가 된다.

0

2

2

4

4

 

기존 배열의 순서와 다르게 작은 값부터 카운트 하기 때문에 Unstable하다.

 

반대로 가장 마지막 값 부터 넣는다면 Stable한 정렬로 구현 가능하다.

 

예제를 풀어보면

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

입력:

출력:

카운팅 정렬을 활용해서 정렬이 잘 된것을 확인 할 수 있다.