주어진 데이터 중에서 자신보다 작거나 같은 값을 갖는 데이터의 개수를 계산하여 정렬할 위치를 찾아 정렬하는 방식
COUNT[a..b]
)을 할당public static void countingSort(int[] array) {
/**
* 입력 배열 내 최대값 구하기
* - 최대값까지만 등장 횟수를 구하기 때문(보조 배열의 크기 제한)
*/
int max = Arrays.stream(array).max().getAsInt();
// 보조 배열을 생성하여 각 값의 등장 횟수 기록
int[] count = new int[max + 1];
for (int number : array) {
count[number]++;
}
// 보조 배열을 업데이트하여 배열 내 값의 누적 등장 횟수 계산
for (int index = 1; index < count.length; index++) {
count[index] += count[index - 1];
}
// 정렬된 결과를 저장할 배열 생성
int[] sortedArray = new int[array.length];
// 입력 배열을 역순으로 순회하면서 정렬된 결과를 저장
for (int index = array.length - 1; index >=0; index--) {
int number = array[index];
int sortedIndex = count[number] - 1; // 현재 값이 정렬된 배열에서 위치해야 할 인덱스
sortedArray[sortedIndex] = number;
count[number]--; // 동일한 값에 대해 정렬된 위치가 변경되었기 때문에 누적 등장 횟수 감소
}
// 정렬된 배열을 입력 배열에 복사
System.arraycopy(sortedArray, 0, array, 0, array.length);
}
public static void countingSort(int[] array) {
// 입력 배열 내 최대값 구하기 : O(n)
int max = Arrays.stream(array).max().getAsInt();
// 보조 배열을 생성하여 각 값의 등장 횟수 기록 : O(n)
int[] count = new int[max + 1];
for (int number : array) {
count[number]++;
}
/**
* 배열 내 값의 누적 등장 횟수 계산 : O(k)
*
* k : 입력 배열의 최대값과 최소값의 차이
*/
for (int index = 1; index < count.length; index++) {
count[index] += count[index - 1];
}
// 정렬된 결과를 저장할 배열 생성
int[] sortedArray = new int[array.length];
// 입력 배열을 역순으로 순회하면서 정렬된 결과를 저장 : O(n)
for (int index = array.length - 1; index >=0; index--) {
int number = array[index];
int sortedIndex = count[number] - 1; // 현재 값이 정렬된 배열에서 위치해야 할 인덱스
sortedArray[sortedIndex] = number;
count[number]--; // 동일한 값에 대해 정렬된 위치가 변경되었기 때문에 누적 등장 횟수 감소
}
// 정렬된 배열을 입력 배열에 복사 : O(n)
System.arraycopy(sortedArray, 0, array, 0, array.length);
}
O(n + n + k + n) = O(3n + k) → O(n+k)
∴ 시간복잡도 : O(n) (단, 입력값의 범위 k가 데이터의 개수 n에 비례하는 경우. 즉, k=O(n))
📖 참고
- 이관용, 김진욱(2024). 알고리즘. 한국방송통신대학교출판문화원