Counting Sort(계수 정렬/ 카운팅 정렬)
-
시간 복잡도 : 𝚶(𝑛)
빠르다는 정렬로 퀵 정렬, 힙 정렬, 합병 정렬이 있는데 이들은 평균 시간 복잡도를 𝚶(nlogn)가지고 있는데 이에 비하면 매우 빠른 시간 복잡도를 가지고 있다. -
기본 메커니즘 : 데이터가 몇번 나왔는지 세주는 것이다. 말 그대로 counting 하는 것이다.
과정 1
array
index 0 1 2 3 4 5 6 7 8 9 10 11 value 7 2 3 5 7 1 4 6 7 5 0 1
array를 한 번 순회하면서 각 값이 나올 때마다 해당 값을 index로 하는 새로운 배열(counting)의 값을 1 증가시킨다.
array[0] = 7 → counting[7] 값을 1증가
array[1] = 2 → counting[2] 값을 1증가
array[2] = 3 → counting[3] 값을 1증가
…
array[11] = 1 → counting[1] 값을 1증가
이렇게 과정을 거치면 다름과 같이 된다.
array
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| value | 7 | 2 | 3 | 5 | 7 | 1 | 4 | 6 | 7 | 5 | 0 | 1 |
counting
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| value | 1 | 2 | 1 | 1 | 1 | 2 | 1 | 3 |
이렇게 countuing 배열은 각 값의 개수가 담겨있는 배열이 된다.
과정 2
counting 배열의 각 값을 누적합으로 변환시킨다.
counting[1] += counting[0]
counting[2] += counting[1]
…
counting[7] += counting[6]
이렇게 우리는 다음과 같은 두 배열을 갖고 있게 된다.
array
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| value | 7 | 2 | 3 | 5 | 7 | 1 | 4 | 6 | 7 | 5 | 0 | 1 |
counting
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| value | 1 | 3 | 4 | 5 | 6 | 8 | 9 | 12 |
여기서 우리가 알수 있는 것은 정렬을 할 경우 counting 배열의 각 값은 (시작점 -1)을 알려준다는 것이다.
과정 3
마지막 단계이다.
위에서 말했던 것처럼 counting 배열의 각 값은 (시작점 -1)을 알려준다 했는데 이는 해당 값에 대응되는 위치에 배정하면 된다는 의미다.
즉 array[0] = 7이고 counting[7]은 12이다. 여기서 counting[7] 의 갑에 1을 빼준 뒤에 해당 값이 새로운 배열의 인덱스 11에 위치한다.
이런식으로 쭉 하면 우리는 array 배열의 정렬된 형태로 result 배열을 얻게 된다.
array
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| value | 7 | 2 | 3 | 5 | 7 | 1 | 4 | 6 | 7 | 5 | 0 | 1 |
counting
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| value | 1 | 3 | 4 | 5 | 6 | 8 | 9 | 12 |
counting[1] - 1
counting
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| value | 1 | 2 | 4 | 5 | 6 | 8 | 9 | 12 |
counting[1] = 2 → result[2]에 1이 위치한다.
result
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| value | 1 |
위의 순서를 반복하면
result
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| value | 0 | 1 | 1 | 2 | 3 | 4 | 5 | 5 | 6 | 7 | 7 | 7 |
이라는 정렬된 result 배열을 얻게 된다.
이 과정에서 두 수를 비교하는 과정이 없기 때문에 빠른 배치가 가능하다. 하지만 몇가지 단점이 존재하는데 새로운 배열을 선언해줘야 한다는 것이다. 이 단점은 꽤 클 수 잇는데 array 안에 있는 max값의 범위에 따라 counting 배열의 길이가 달라지게 된다. 예로 들어 10개의 원소를 정렬하고자 하는데 수의 범위가 0 ~ 1억이라면 메모리가 매우 낭비가 된다.
퀵 정렬이나 병합정렬 등이 선호되는 이유도 여기에 있다.
퀵 정렬의 경우 시간복잡도 평균값이 𝚶(nlogn) 빠른 편이면서 배열도 하나만 사용하고 공간 복잡도는 O(n)으로 시간과 메모리 둘 다 효율적이라는 점이다.
구현하기[Java]
public class CountingSort {
public static void main(String[] args){
int[] array = new int[100]; // 수열의 원소 : 100개
int[] counting = new int[31]; // 수의 범위 : 0 ~ 30
int[] result = new int[100]; // 정렬 될 배열
for(int i = 0; i < array.length; i++) {
array[i] = (int)(Math.random()*31); // 0 ~ 30
}
// Counting Sort
// 과정 1
for(int i = 0; i < array.length; i++) {
// array 의 value 값을 index 로 하는 counting 배열 값 1 증가
counting[array[i]]++;
}
// 과정 2
for(int i = 1; i < counting.length; i++) {
// 누적 합 해주기
counting[i] += counting[i - 1];
}
// 과정 3
for(int i = array.length - 1; i >= 0; i--) {
/*
* i 번쨰 원소를 인덱스로 하는 counting 배열을 1 감소시킨 뒤
* counting 배열의 값을 인덱스로 하여 result에 value 값을 저장한다.
*/
int value = array[i];
counting[value]--;
result[counting[value]] = value;
}
/* 비교 출력 */
// 초기 배열
System.out.println("array[]");
for(int i = 0; i < array.length; i++) {
if(i % 10 == 0) System.out.println();
System.out.print(array[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 < result.length; i++) {
if(i % 10 == 0) System.out.println();
System.out.print(result[i] + "\t");
}
System.out.println();
}
}정리
Counting Sort는 각 배열 원소끼리 직접 비교하는 것이 아닌 인덱스를 갖고 위치를 찾아나가는 것이다. 위의 예시는 비교를 위해 array와 result 배열이 존재했지만, 수의 범위를 알고있고 입출력만 하는 것이라면 array에 0번째부터 입력하는게 아니라 counting처럼 입력 받자마자 해당 값을 array 배열의 인덱스를 사용하여 array 배열 값을 증가시킨 뒤, 누적 합 부분을 skip하고 바로 array[0] 부터 해당 인덱스의 값이 0 이 될 때 까지 인덱스를 출력해주면 된다.
