[Algorithm] 카운팅(계수) 정렬 개념

원소간 비교하지 않고 각 원소가 몇개 등장하는지 갯수를 세서 정렬하는 방법. 모든 원소는 양의 정수여야 한다.

시간복잡도는 O(n+k) 로 퀵정렬, 병합정렬에 비해 일반적으로 빠르다.

 

정렬을 위한 길이 n의 배열 하나, 계수를 위한 길이 k의 배열 하나. 총 2개의 별도 배열을 필요로한다.

O(n+k) 의 공간복잡도를 가진다.

* 카운팅 정렬 단계

1. 배열 안에 있는 원소 종류만큼의 새로운 배열을 생성하고 0으로 초기회시킨다.
   • 만약 배열에 [0, 1, 3, 1, 3]이 있다면 0~3 크기의 배열 생성
2. 각 원소의 갯수를 계산하여 배열 안에 담는다
   • 0은 1개이므로 c[0]=1, 1은 2개이므로 c[1] = 2, 2는 존재하지 않으므로 0
3. 누적합을 이용하여 계산한다. (배열에 값이 들어갈 위치를 선정하는 것)

따라서 c[1]에는 4가 들어간다.

• c[1] = c[0] + c[1]
• c[2] = c[1] + c[2]
• c[3] = c[2] + c[3]
• c[4] = c[3] + c[4]

최종적으로 누적합 된 배열은 위와 같다.

• 0은 0번째부터 1번째 사이까지 위치한다. (0)
• 1은 1번째부터 4번째 사이까지 위치한다 (1, 2, 3)
• 2는 4번째에서 4번째 사이까지 위치한다 (없음)
• 3은 4번째에서 6번째까지 위치한다. (4, 5)

4. 정렬시키기 위한 배열이 하나 더 필요하다. 기존 배열과 같은 크기를 가지는 임시 배열을 하나 더 생성한다.
   • 기존 배열의 오른쪽부터 왼쪽으로 진행해야 안정정렬이 가능하다.
5. 누적합 배열 c에 있는 것은 위치를 의미한다. 누적합에 있는 수를 -1 해주고 그 수의 위치로 보내며 정렬한다.

6. 위의 그림에서 누적합 c[1]이 의미하는 것은 1은 index 1부터 3까지 위치할 수 있다는 것이다. (1, 2, 3)

   • 따라서 aux[3]에 1을 넣는다.

7. 그 다음 3에 대해 정렬을 수행한다.

   • 다음 원소가 3이고 c[3]은 5이므로(6에서 -1를 해주어야 한다) aux[5]에 3을 넣는다.

 

위와 같은 과정을 반복하면 정렬이 완료된다.

 

참고한 곳: https://yaboong.github.io/algorithms/2018/03/20/counting-sort/