서론
카운팅 정렬(Counting Sort)은 정수 기반의 데이터를 정렬하기 위해 설계된 효율적인 정렬 알고리즘이다.
이 알고리즘은 각 원소의 등장 횟수를 계산하여 정렬을 수행하며, 특정 조건에서 매우 빠르게 동작할 수 있다.
이 글에서 카운팅 정렬의 개념과 동작 방식, 장점 및 단점을 정리하고자 한다.
카운팅 정렬이란
카운팅 정렬은 입력 데이터의 범위가 상대적으로 좁을 때 효과적인 정렬 알고리즘이다. 이 알고리즘은 각 원소가 등장하는 횟수를 기록하고, 이 빈도 정보를 바탕으로 정렬된 결과를 빠르게 생성한다. 카운팅 정렬의 주요 아이디어는 데이터를 직접 정렬하는 대신, 각 값의 출현 빈도를 계산하여 원래 배열의 정렬을 수행하는 것이다.
카운팅 정렬 동작 과정
카운팅 정렬은 다음과 같은 단계로 이루어진다.
- 최댓값 찾기:
- 배열에서 가장 큰 값을 찾는다. 이 값은 카운트 배열의 크기를 결정하는 데 필요하다.
- 예를 들어, 배열의 원소가 0부터 10까지의 값이면, 카운트 배열은 11개의 요소를 가진다.
- 카운트 배열 생성 및 초기화:
- 최댓값 + 1 크기의 카운트 배열을 생성하고, 모든 값을 0으로 초기화한다.
- 이 배열은 각 원소가 얼마나 자주 등장하는지를 기록한다.
- 빈도 계산:
- 원래 배열을 순회하면서 각 원소의 빈도를 카운트 배열에 기록한다.
- 예를 들어, 배열 [1, 5, 5, 2]가 있다면, 카운트 배열은 [0, 1, 1, 0, 0, 2]로 업데이트된다.
- 누적 카운트 배열 생성:
- 카운트 배열을 누적 카운트 배열로 변환하여 각 원소의 위치를 결정한다.
- 누적 카운트 배열의 각 인덱스는 해당 값이 정렬된 배열에서의 최종 위치를 나타냅니다.
- 정렬된 배열 생성:
- 원래 배열을 역순으로 순회하면서 카운트 배열을 참조하여 정렬된 배열을 생성한다.
- 이렇게 하면 같은 값을 가지는 원소들이 원래 배열에서의 순서를 유지하며 정렬된다.
카운팅 정렬 예시 :
1. 최대 값 찾기

- 정렬하고자 하는 배열의 최대값을 찾는다.
- A 배열의 최대값은 10이다.
2. 카운팅 배열 생성

- 배열의 각 원소의 등장 횟수를 기록하기 위해 카운팅 배열을 생성한다.
- 카운팅 배열의 크기는 A 배열의 최대값인 (10 + 1)로 선언한다.
- 따라서 카운팅 배열의 크기는 11이 된다. (0부터 10까지)
- 0으로 초기화 되지만 가독성을 위해 제외하였다.
3. 원소의 빈도 수 저장

- 배열 A를 순회하면서 각 원소의 빈도 수를 카운팅 배열에 저장한다.
- 원소 1: B[1]를 1로 증가
- 원소 6: B[6]를 1로 증가
- 원소 5: B[5]를 1로 증가 (다시 등장하므로 2로 증가)
- 원소 4: B[4]를 1로 증가
- 원소 10: B[10]를 1로 증가
- 원소 8: B[8]를 1로 증가
업데이트 된 카운팅 배열 $B=[0,1,0,0,1,2,1,0,1,0,1]$
4. 누적 합 계산

- B 배열을 순회하면서 현재 원소값에 이전 원소의 값을 더하여준다.
- 누적 합을 계산하여 각 숫자가 정렬된 배열에서 시작해야 할 인덱스를 결정한다.
- 숫자 1은 인덱스 1 ~ 3에 위치한다.
- 숫자 2는 인덱스 4에 위치한다.
- 숫자 4는 인덱스 5에 위치한다.
- 숫자 5는 인덱스 6 ~ 7에 위치한다.
- 숫자 6은 인덱스 8 ~ 9에 위치한다.
- 숫자 10은 인덱스 10에 위치한다.
5. 정렬

처리 과정:
먼저 정렬된 배열을 저장할 배열 C를 선언해야한다. $C.length == A.length$
- 첫 번째 요소:
- 숫자 가져오기: A 배열의 마지막 원소인 $8$을 가져온다
- 위치 찾기: B[8] 값은 6이다. 이 값은 숫자 $8$이 C 배열에서 위치할 자리이다.
- 배치하기: C 배열의 인덱스 6−1=5 위치에 숫자 8을 배치합니다.
- 위치 값 감소: 이제 B[8] 값을 1 감소시켜 다음에 숫자 8이 나오면 올바른 위치에 배치되도록 한다.
- 다음 요소 :
- 숫자 가져오기 : A 배열의 두 번째 마지막 원소인 $10$을 가져온다.
- 위치 찾기 : B[10] 값은 7이다. 이 값은 숫자 $10$이 C 배열에서 위치할 자리이다.
- 배치하기 : C 배열의 인덱스 7-1=6 위치에 숫자 $10$을 배치한다.
- 위치 값 감소: 이제 B[10] 값을 1 감소시켜 다음에 숫자 $10$이 나오면 올바른 위치에 배치되도록 한다.
- 다음 요소:
- 숫자 가져오기: A배열의 세 번째 마지막 원소인 4를 가져온다.
- 위치 찾기: B[4]의 값은 2이다.
- 배치하기: C 배열의 인덱스 2−1=1 위치에 숫자 4를 배치한다.
- 위치 값 감소: B[4] 값을 1 감소시킨다.
... 생략
- 마지막 요소:
- 숫자 가져오기: A배열의 첫 번째 요소인 1을를 가져온다.
- 위치 찾기: B[1]의 값은 1이다.
- 배치하기: C 배열의 인덱스 1−1=0 위치에 숫자 1를 배치한다.
- 위치 값 감소: B[1] 값을 1 감소시킨다.
위와 같은 동작을 반복하여 배열을 정리한다.
카운팅 정렬 구현
public static int[] countingSort(int[] arr) {
int maxValue = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > maxValue) {
maxValue = arr[i];
}
}
int[] countArr = new int[maxValue + 1];
for (int i = 0; i < arr.length; i++) {
countArr[arr[i]]++;
}
for (int i = 1; i < countArr.length; i++) {
countArr[i] += countArr[i - 1];
}
int[] sortedArr = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
int num = arr[arr.length - i - 1];
sortedArr[countArr[num] - 1] = num;
countArr[num]--;
}
return sortedArr;
}
}
카운팅 정렬(Counting Sort)의 장단점
장점
- 선형 시간 복잡도:
- 카운팅 정렬은 데이터의 범위가 작을 때 $O(n+k)$의 시간 복잡도를 가진다.
- 여기서 $n$은 입력 데이터의 크기, $k$는 입력 데이터 중 최대 값이다.
- 따라서 특정 조건에서는 매우 효율적인 알고리즘이다.
- 간단한 구현:
- 카운팅 정렬은 비교 기반 정렬 알고리즘이 아니므로 구현이 간단한다.
- 각 숫자의 등장 횟수를 카운팅하고 그 정보를 사용해 배열을 정렬한다.
- 안정 정렬:
- 카운팅 정렬은 안정 정렬이다.
- 동일한 값을 가진 요소들의 순서가 정렬 전후에도 유지된다. 이는 중복된 요소가 있는 데이터에서 유리하다.
단점
- 제한된 데이터 유형:
- 카운팅 정렬은 정수 또는 정수로 표현할 수 있는 데이터에만 적합하다.
- 실수나 복잡한 데이터 유형에는 적용하기 어렵다.
- 큰 범위의 데이터에 비효율적:
- 데이터의 최대 값 $k$ 가 크다면, 카운팅 배열의 크기 또한 커지게 되어 메모리 사용량이 비효율적일 수 있다.
- 예를 들어, 범위가 0부터 1,000,000인 데이터를 정렬하려면 매우 큰 카운팅 배열이 필요하다.
- 메모리 낭비:
- 데이터의 최대 값과 최소 값 사이에 많은 빈 값이 있는 경우 메모리를 비효율적으로 사용하게 된다.
- 정렬 범위의 제약:
- 카운팅 정렬은 데이터의 범위가 제한적일 때만 효과적이다.
- 범위가 넓어지면, 시간 및 공간 효율성 측면에서 다른 정렬 알고리즘에 비해 비효율적일 수 있다.
시간 복잡도 분석
1. 최대값 찾기
- 배열에 최대값을 찾는 과정은 입력 배열을 한 번 순회하면서 이루어지므로 시간 복잡도는 $O(n)$이다.
2. 카운트 배열 생성 및 초기화
- 최댓값 $k$ 를 이용하여 크기가 $k+1$인 카운트 배열을 생성하고 초기화하는 과정은 $O(k)$의 시간 복잡도를 가진다.
3. 빈도 계산
- 입력 배열을 다시 순회하며 각 원소의 빈도를 카운트 배열에 저장하는 과정으로, 시간 복잡도는 $O(n)$이다.
4. 누적 합 계산
- 카운트 배열을 누적 합 배열로 변환하는 과정으로, 시간 복잡도는 $O(k)$ 이다.
5. 정렬된 배열 생성
- 입력 배열을 역순으로 순회하면서 각 원소를 정렬된 배열에 배치하는 과정으로, 시간 복잡도는 $O(n)$이다.
총 시간 복잡도
각 단계를 종합하면 카운팅 정렬의 전체 시간 복잡도는 다음과 같다.
$O(n)+O(k)+O(n)+O(k)+O(n)=O(n+k)$
- $n$은 입력 배열의 크기,
- $k$는 입력 배열의 최대 값이다.
따라서, 카운팅 정렬의 시간 복잡도는 $O(n+k)$ 이다.
결론
카운팅 정렬은 특정한 상황에서 매우 빠르게 동작할 수 있는 알고리즘이다. 정렬을 매우 빠르게 수행할 수 있지만, 데이터의 특성과 범위를 고려하여 사용해야 한다. 데이터가 정수로 이루어져 있고, 데이터의 최대값이 데이터의 크기 $n$에 비해 크지 않으며 메모리가 충분히 여유가 있는 경우 카운팅 정렬을 사용하면 빠르게 정렬을 할 수 있다.
이러한 조건을 만족할 때 카운팅 정렬은 효율적인 정렬 알고리즘으로, 특히 대량의 정수 데이터나 범위가 제한된 데이터를 다룰 때 매우 유용하다. 따라서, 카운팅 정렬을 적용할 때는 데이터의 범위와 메모리 사용량을 신중히 고려하여 적절히 활용하는 것이 중요할거 같다.
관련 문제
'PS > 탐색' 카테고리의 다른 글
| [알고리즘 | 탐색] 이진 탐색 활용 Lower Bound & Upper Bound 정리 (0) | 2024.08.09 |
|---|---|
| [알고리즘 | 정렬] 선택 정렬 (Selection Sort) 정리 (0) | 2024.08.08 |
| [알고리즘 | 탐색] 이진 탐색 (Binary Search) 정리 (0) | 2024.08.07 |
