카운팅 정렬(Counting Sort)이란?
카운팅 정렬(Counting Sort)이란?
카운팅 정렬은 원소의 값이 특정 범위 내에 있을 때 매우 빠른 속도로 정렬을 수행할 수 있는 알고리즘입니다.
- 배열의 원소가 가령 0 이상 K 이하의 범위를 가진다면, 크기가 K+1인 ‘카운트 배열(count array)’을 만든 뒤 각 원소가 몇 번 등장하는지 세어 저장합니다.
- 이후 카운트 배열을 적절히 누적 합 형태로 변환하거나, 세어진 횟수를 바탕으로 원소들의 최종 위치를 계산하여 결과를 정렬된 형태로 재배치합니다.
카운팅 정렬은 분할 정복을 사용하는 퀵 정렬, 합병 정렬(Merge Sort), 힙 정렬(Heap Sort) 등과 달리 비교(comparison) 없이 정렬을 수행하기 때문에 특성이 다릅니다.
카운팅 정렬의 특징
- 빠른 정렬 속도
- 원소의 값의 범위(0~K)가 N(원소 개수)과 비슷하거나 작다면, O(N + K) 라는 매우 빠른 시간 복잡도를 가집니다.
- 반면 값의 범위가 매우 클 경우(K가 너무 크다면), 별도의 대안을 고려해야 합니다.
- 비교 연산을 사용하지 않음
- 일반적인 비교 기반 정렬 알고리즘(퀵 정렬, 병합 정렬 등)은 최선의 경우 O(N log N) 이나, 카운팅 정렬은 원소의 값 범위를 알고 있을 때 비교 없이 더 효율적으로 정렬할 수 있습니다.
- 추가 공간 필요
- 원소들의 범위를 카운팅하기 위한 추가 공간(카운트 배열)이 필요합니다.
- 따라서 공간 복잡도가 O(K)가 되며, K가 매우 큰 경우 비효율적일 수 있습니다.
카운팅 정렬의 동작 원리
1. 값의 범위 확인
먼저 정렬 대상 리스트의 원소들이 가질 수 있는 최소값 ~ 최대값 범위를 확인합니다.
(예: 19, 혹은 010,000 등)
2. 카운트 배열 생성
해당 범위를 나타낼 수 있는 크기의 배열(예: K+1)을 생성합니다. 모든 값을 0으로 초기화합니다.
3. 등장 횟수 세기
정렬 대상 리스트를 순회하며, 각 원소가 등장할 때마다 카운트 배열에서 해당 원소 인덱스를 +1 증가시킵니다.
4. 누적 합(옵션)
**안정 정렬(Stable Sort)**을 구현하거나, 정렬 결과를 특정 배열에 재배치하기 위해서는 “누적 합” 과정을 거칩니다.
- 카운트 배열의 각 원소에 대해 이전까지의 등장 횟수를 더해 실제로 몇 번째 위치에 배치될 원소인지를 계산합니다.
5. 결과 배열에 재배치
원소를 뒤에서부터(혹은 앞에서부터) 순회하며 누적 합 배열을 참조해 결과 배열의 올바른 위치에 배치해 넣습니다.
이후 결과 배열이 카운팅 정렬을 완료한 최종 정렬 리스트가 됩니다.
시간 복잡도 & 공간 복잡도
- 시간 복잡도:
- 카운트 배열을 채우는 과정 O(N),
- (필요하다면) 누적 합 배열을 만드는 과정 O(K),
- 다시 원소를 배치하는 과정 O(N).
- 따라서 총 O(N + K) 의 시간 복잡도를 가집니다.
- 공간 복잡도:
- 카운트 배열을 저장하기 위해 O(K) 크기의 추가 공간이 필요합니다.
- 정렬 대상 배열과 별개로 결과 배열까지 만든다면 결과적으로는 O(N + K)가 될 수 있습니다.
간단한 예시
예를 들어, 정렬해야 할 원소가 다음과 같다고 가정해 봅시다.
csharp
[3, 6, 4, 2, 3, 6, 9, 6, 1, 3]
- 이 배열의 값이 모두 1 이상 9 이하라고 가정해봅시다(K=9).
- 크기 10(인덱스 0~9)의 카운트 배열을 만들고, 모든 값을 0으로 초기화합니다.
1) 카운트 배열 채우기
- 0열 선택0열 다음에 열 추가
- 1열 선택1열 다음에 열 추가
- 2열 선택2열 다음에 열 추가
- 3열 선택3열 다음에 열 추가
- 4열 선택4열 다음에 열 추가
- 5열 선택5열 다음에 열 추가
- 6열 선택6열 다음에 열 추가
- 7열 선택7열 다음에 열 추가
- 8열 선택8열 다음에 열 추가
- 9열 선택9열 다음에 열 추가
- 10열 선택10열 다음에 열 추가
- 0행 선택0행 다음에 행 추가
- 1행 선택1행 다음에 행 추가
|
인덱스(값)
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
초기값
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
- 셀 병합
- 행 분할
- 열 분할
- 너비 맞춤
- 삭제
- 배열을 순회하며 등장 횟수를 증가
- 3 -> count[3] += 1
- 6 -> count[6] += 1
- 4 -> count[4] += 1
- 2 -> count[2] += 1
- 3 -> count[3] += 1
- 6 -> count[6] += 1
- 9 -> count[9] += 1
- 6 -> count[6] += 1
- 1 -> count[1] += 1
- 3 -> count[3] += 1
- 0열 선택0열 다음에 열 추가
- 1열 선택1열 다음에 열 추가
- 2열 선택2열 다음에 열 추가
- 3열 선택3열 다음에 열 추가
- 4열 선택4열 다음에 열 추가
- 5열 선택5열 다음에 열 추가
- 6열 선택6열 다음에 열 추가
- 7열 선택7열 다음에 열 추가
- 8열 선택8열 다음에 열 추가
- 9열 선택9열 다음에 열 추가
- 10열 선택10열 다음에 열 추가
- 0행 선택0행 다음에 행 추가
- 1행 선택1행 다음에 행 추가
|
인덱스(값)
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
최종
|
0
|
1
|
1
|
3
|
1
|
0
|
3
|
0
|
0
|
1
|
- 셀 병합
- 행 분할
- 열 분할
- 너비 맞춤
- 삭제
- 해석:
- 값 1은 1개, 값 2는 1개, 값 3은 3개, 값 4는 1개, 값 6은 3개, 값 9는 1개 등장
2) 누적 합 만들기(옵션)
누적 합을 만들면, 값 i가 최종 정렬된 배열의 어디까지를 차지하는지를 알 수 있게 됩니다. (안정 정렬을 구현하거나, 뒤에서부터 원소를 배치할 때 필요)
- 누적 합 과정
- 0열 선택0열 다음에 열 추가
- 1열 선택1열 다음에 열 추가
- 2열 선택2열 다음에 열 추가
- 3열 선택3열 다음에 열 추가
- 4열 선택4열 다음에 열 추가
- 5열 선택5열 다음에 열 추가
- 6열 선택6열 다음에 열 추가
- 7열 선택7열 다음에 열 추가
- 8열 선택8열 다음에 열 추가
- 9열 선택9열 다음에 열 추가
- 10열 선택10열 다음에 열 추가
- 0행 선택0행 다음에 행 추가
- 1행 선택1행 다음에 행 추가
- 2행 선택2행 다음에 행 추가
|
인덱스
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
count
|
0
|
1
|
1
|
3
|
1
|
0
|
3
|
0
|
0
|
1
|
|
누적합
|
0
|
1
|
2
|
5
|
6
|
6
|
9
|
9
|
9
|
10
|
- 셀 병합
- 행 분할
- 열 분할
- 너비 맞춤
- 삭제
- 예: 값 3 까지는 전체 중 5개의 자리(인덱스 0~4 범위)를 차지한다는 의미가 됩니다.
3) 결과 배열에 재배치
- 원본 배열을 뒤에서부터 순회: [3, 6, 4, 2, 3, 6, 9, 6, 1, 3]
- 각 원소 x에 대해 누적합 배열의 count[x] 값을 확인 후, 그 위치에 배치하고 count[x]를 1 감소시키면 안정적으로(Stable) 정렬 가능합니다.
이 과정을 거친 최종 결과는
csharp
[1, 2, 3, 3, 3, 4, 6, 6, 6, 9]
가 됩니다.
마무리
**카운팅 정렬(Counting Sort)**은 비교 기반 정렬 알고리즘과 달리, 데이터 범위를 미리 알고 있고 그 범위가 상대적으로 작을 때 매우 빠르고 효율적인 정렬을 제공해주는 알고리즘입니다.
- 시간 복잡도가 O(N + K) 로, N과 K가 비슷한 크기를 가질 때는 일반적인 O(N log N) 정렬 알고리즘을 능가할 수 있습니다.
- 하지만 범위가 너무 큰 경우에는 저장 공간과 시간 모두 비효율적이 될 수 있으니, 상황에 맞춰 사용하는 것이 핵심입니다.
퀵 정렬과 함께 카운팅 정렬, 병합 정렬, 힙 정렬 등 다양한 정렬 기법을 공부해 두면, 알고리즘 문제 해결 시 데이터 범위나 정렬 필요 조건(안정 정렬 여부 등)에 따라 적절한 정렬 알고리즘을 선택할 수 있게 됩니다.
긴 글 읽어주셔서 감사합니다!
다음번에 더 다양한 알고리즘과 문제 해결 전략으로 찾아뵙겠습니다.