참고 포스팅
카운팅 정렬이라... 여러 포스팅 글을 검색하여 읽어봤지만 처음 들어보는 정렬 방식이었습니다.
카운팅 정렬은 수많은 정렬 알고리즘 중 시간복잡도가 O(n)으로 가장 좋은 성능을 보여주는 알고리즘 입니다.
👀정렬 방법
카운팅 정렬의 기본 메커니즘은 아주 단순합니다. 데이터의 값이 몇번이나 나왔는지를 세주는 것입니다.
우선, 아래와 같은 배열이 있습니다.
1) 배열을 순회하면서 값을 확인하여 해당 값을 index로 되어 있는 counting 배열의 값을 1 증가시켜줍니다.
arr[0] = 7 인 경우, counting[7]++ 가 됩니다.
arr[1] = 2 인 경우, counting[2]++ 가 됩니다.
...
위 처리 과정이 끝나면, 다음의 그림처럼 나옵니다.
counting 배열은 말 그대로, 배열 ㅇ나에 담긴 요소를 index로 하여금 갯수를 세어주는 배열입니다.
2) counting 배열의 각 값을 누적합으로 변환시켜줍니다.
누적합은 시간 복잡도 관점에서 큰 이득을 가져다 줍니다. 미리 계산을 해놓은 뒤 필요시에 해당 배열에서 가져다 쓰기만 하면 되기 때문에 훨씬 시간복잡도가 작아지게 됩니다.
누적합을 연산하면 다음과 같은 두 배열이 결과적으로 생성됩니다.
3) counting 값에 -1을 해준 뒤, 각 해당 값에 대응되는 위치에 배정하면 정렬이 완료됩니다.
쉽게 설명하면 다음과 같습니다.
array[0] = 7이고, counting[7] = 12 입니다. → counting[7] = 11 → idex = 11에 7을 넣어줍니다.
array[1] = 2이고, counting[2] = 4 입니다. → counting[2] = 3 → idex = 3에 2를 넣어줍니다.
...
" 다만, 안정적으로 배열을 정렬하기 위해서는 배열의 인덱스 마지막 순서부터 차례로 순회하는 것이 좋습니다. "
위 과정을 반복하면 다음과 같은 배열이 완성됩니다.
result 배열은 array 배열의 정렬된 형태로 나타납니다.
☢️ 단점
counting 배열이라는 새로운 배열을 선언해줘야 한다는 단점이 있다. 이는 array 내부 요소의 범위가 커지면 커질수록 counting 배열의 요소 갯수가 커지기 때문에 이를 고려하여 사용해야 한다.
예를 들어, 10개의 원소를 정렬하고자 할 때, 수의 범위가 최대 10억 이라면, 10억의 길이의 counting 배열이 생성되어야 하기 때문에, 메모리 낭비가 심해집니다.
즉, Counting Sort가 효율적인 상황에엇 쓰려면 수열의 길이보다 수의 범위가 극단적으로 크면, 메모리가 크게 낭비될 수 있습니다. 이러한 경우에는 차라리 O(nlogn)의 퀵정렬 이나 병합정렬을 사용하는 것이 더 좋습니다.
👀구현
public class 카운팅정렬{
public static void main(String[] args) {
int[] arr = new int[100];
int[] counting = new int[31];
int[] res = new int[100];
for(int i=0; i< arr.length; i++){
arr[i] = (int)(Math.random()*31); // 0 ~ 30
}
// counting 정렬
// 과정1 - counting 배열에 요소 갯수
for(int i=0; i < arr.length; i++){
counting[arr[i]]++;
}
// 과정2 - 누적합
for(int i=1; i < counting.length; i++){
counting[i] += counting[i-1];
}
// 과정3 - arr 배열 내 counting에 해당하는 요소에 -1 후 result에 담기
for(int i=0; i < arr.length; i++){
int value = arr[i];
counting[value]--;
res[counting[value]] = arr[i];
}
/* 비교 출력 */
// 초기 배열
System.out.println("array[]");
for(int i = 0; i < arr.length; i++) {
if(i % 10 == 0) System.out.println();
System.out.print(arr[i] + "\t");
}
System.out.println("\n\n");
// Counting 배열
System.out.println("counting[]");
for(int i = 0; i < counting.length; i++) {
if(i % 10 == 0) System.out.println();
System.out.print(counting[i] + "\t");
}
System.out.println("\n\n");
// 정렬된 배열
System.out.println("result[]");
for(int i = 0; i < res.length; i++) {
if(i % 10 == 0) System.out.println();
System.out.print(res[i] + "\t");
}
System.out.println();
}
}출력 결과
array[]
3 29 12 13 20 27 7 7 26 11
1 10 30 12 10 2 6 22 1 15
1 28 9 29 14 16 21 21 13 14
24 23 21 22 4 24 10 11 30 9
23 13 1 23 20 19 17 24 3 1
10 20 16 4 13 6 26 18 19 8
8 1 1 22 12 20 0 9 25 7
24 18 23 27 4 30 24 6 1 2
30 4 25 24 8 24 24 7 12 4
21 22 20 10 25 13 9 2 18 5
counting[]
0 1 9 12 14 19 20 23 27 30
34 39 41 45 50 52 53 55 56 59
61 66 70 74 78 86 89 91 93 94
96
result[]
0 1 1 1 1 1 1 1 1 2
2 2 3 3 4 4 4 4 4 5
6 6 6 7 7 7 7 8 8 8
9 9 9 9 10 10 10 10 10 11
11 12 12 12 12 13 13 13 13 13
14 14 15 16 16 17 18 18 18 19
19 20 20 20 20 20 21 21 21 21
22 22 22 22 23 23 23 23 24 24
24 24 24 24 24 24 25 25 25 26
26 27 27 28 29 29 30 30 30 30