카운팅 정렬(Counting Sort)
- 카운팅 정렬의 기본 메커니즘은 데이터의 값이 몇 번 나왔는지를 세주는 것이다.
- 시간 복잡도는 O(N)으로 뛰어난 성능을 보여주는 정렬 알고리즘이다.
- (일반 배열을 정렬하는 경우) 배열의 값 중에 음수가 있으면 사용할 수 없다는 단점이 있다.
1) Data 배열에서의 최댓값을 최대 인덱스로 갖는 counts 배열 생성 후, data에 각 인덱스에 해당하는 숫자가 몇 번 등장하는지 누적 카운팅
2) 뒤에서 부터 탐색하며, data 배열의 값에 해당하는 count 배열 인덱스로 가서 값을 -1 해준 뒤, result 배열에 해당 값의 인덱스로 가서 data 배열의 값 입력. data 배열의 0번째 index에 도달할 때 까지 반복.
코드 구현
public static countingSort() {
int[] arr = new int[20];
for(int i = 0; i < 20; i++) {
int rdm = (int) (Math.random() * 100) + 1;
arr[i] = rdm;
}
// arr 배열에서 최댓값을 찾음
int max = 0;
for(int x : arr) {
max = Math.max(max, x);
}
int[] counts = new int[max + 1];
int[] result = new int[arr.length];
// arr에 counts 배열의 인덱스에 해당하는 값들이 몇 번 나오는지 카운트
for(int x : arr) {
counts[x]++;
}
// counts 배열을 누적합으로 변경
for(int i = 1; i < counts.length; i++) {
counts[i] += counts[i - 1];
}
// arr 배열 뒤에서부터 돌면서 result에 정렬한 값 넣기.
for(int i = result.length - 1; i >= 0; i--) {
counts[arr[i]]--;
result[counts[arr[i]]] = arr[i];
}
}public <T extends Comparable<T>> List<T> sort(List<T> list) {
Map<T, Integer> frequency = new TreeMap<>();
List<T> sortedArray = new ArrayList<>(list.size());
// 배열의 원소들의 개수를 카운트해서 TreeMap에 입력
list.forEach(v -> frequency.put(v, frequency.getOrDefault(v, 0) + 1));
// sortedArray에 값 저장
for (Map.Entry<T, Integer> element : frequency.entrySet()) {
for (int j = 0; j < element.getValue(); j++) {
sortedArray.add(element.getKey());
}
}
return sortedArray;
}private static <T extends Comparable<T>> List<T> streamSort(List<T> list) {
return list
.stream()
.collect(toMap(k -> k, v -> 1, (v1, v2) -> v1 + v2, TreeMap::new))
.entrySet()
.stream()
.flatMap(entry ->
IntStream
.rangeClosed(1, entry.getValue())
.mapToObj(t -> entry.getKey())
)
.collect(toList());
}
