Counting Sort
동작 원리
주어진 배열에서 가장 큰 값을 찾는다
누적합을 저장하기 위해 배열에서 가장 큰 값에 1을 더한 크기의 배열을 생성한다
배열의 요소를 카운트하여 누적합 배열에 저장한다
배열의 왼쪽 요소부터 값을 더하며 증가하는 누적합을 구성한다
정렬되지 않은 원본 배열의 요소를 꺼내어 자신의 값에 해당하는 누적합 배열의 인덱스를 조회하고, 누적합 배열 인덱스에 해당하는 값에서 -1 을 한 좌표에 정렬 결과를 담을 배열에 저장한다
5번 과정을 반복하여 배열의 값을 모두 정렬 시킨다
구현
package sort;
public class CountingSort {
public static void main(String[] args) {
CountingSort countingSort = new CountingSort();
int[] A = {2, 5, 3, 0, 2, 3, 0, 3};
int[] sorted = countingSort.sort(A);
countingSort.printArray(sorted);
}
public void printArray(int[] A) {
for (int num : A) {
System.out.print(num + " ");
}
}
public int[] sort(int[] A) {
int n = A.length;
// 최대값 찾기
int k = getMax(A);
int[] count = new int[k + 1];
int[] output = new int[n];
// 각 요소의 빈도 계산
for (int i = 0; i < n; i++) {
count[A[i]]++;
}
// 누적 합 계산
for (int i = 1; i <= k; i++) {
count[i] += count[i - 1];
}
// 출력 배열에 정렬된 요소 배치
for (int i = n - 1; i >= 0; i--) {
output[count[A[i]] - 1] = A[i];
count[A[i]]--;
}
return output;
}
private int getMax(int[] A) {
int max = A[0];
for (int num : A) {
if (num > max) {
max = num;
}
}
return max;
}
}풀이
주어진 배열에서 최대 값을 찾는다.
최대 값에서 1을 더하여, 누적합을 저장할 배열의 크기를 지정하여 할당한다.
반환할 결과 배열을 생성해도 되고, 원본 배열에 복사해도 되기 때문에 구현 방법에 맡기지만, 위 구현에서는 결과를 반환하기 위해 결과 배열도 생성한다.
누적합을 저장할 배열에 각 요소마다 몇 번씩 등장하는지 갯 수를 센 뒤, 왼쪽의 값을 쭉 더해나가는 누적합을 완성시킨다.
배열의 뒤에서부터 값을 하나씩 순회하며, 조회된 값을 누적합 배열의 인덱스로 접근하고 그 접근 결과를 -1 하여 반환할 배열에 배치한다.
위 과정을 반복하여 뒤에서부터 0번째 인덱스까지 모두 순회하면 정렬이 완료된다.
선택 가이드
시간 복잡도
모든 데이터에서 최대 값 검색 N 회, 요소 갯 수 카운트 N 회, 누적합 N -1 회, 결과 배열로 이동 N 회의 흐름을 따르며 O(n) 알고리즘이다.
장점
요소가 등장한 횟수를 세기 때문에 안정 정렬 알고리즘이다.
값을 비교하는 알고리즘이 아닌 계산 하는 알고리즘은 비교 알고리즘보다 훨씬 빠른 속도를 자랑한다.
단점
배열의 요소 중 큰 값이 클수록 배열의 크기가 커지기 때문에 비효율적이다.
배열 요소를 중간에 저장하기 위해 추가적인 메모리 공간을 필요로한다.
참고 자료
Last updated