Reference URL : https://st-lab.tistory.com/104
🌱 카운팅 정렬/계수 정렬
카운팅 정렬은 수 많은 정렬 알고리즘 중 시간복잡도가 O(n)으로 엄청난 성능을 보여주는 알고리즘이다.
🌿 정렬 방법
카운팅 정렬의 기본 메커니즘은 데이터의 값이 몇 번 나왔는지를 세주는 것이다.
먼저 아래와 같은 배열이 있다고 가정해보자.
📌 과정 1
array를 한 번 순회하면서 각 값이 나올 때마다 해당 값을 index 로 하는 새로운 배열(counting)의 값을 1 증가시킨다.
📌 과정 2
counting 배열의 각 값을 누적합으로 변환시킨다.
결과적으로 다음과 같은 두 배열을 갖게 되는 것이다.
여기서 알 수 있는 것은 정렬을 할 경우 counting 배열의 각 값은 (시작점 - 1)을 알려준다는 것이다. 즉, 각 값이 시작하는 위치(뒷쪽부터)를 알려준다는 것이다.
누적합의 목적은 큰 인덱스에 큰 값이 들어가도록 하여 결과 배열의 뒷쪽에 큰 값이 가도록 하기 위함이다.
📌 과정 3
원본 배열에서 선택된 값의 인덱스를 counting 배열에서 찾으면 그 값의 개수를 알 수 있다. 앞서, 누적합을 통해 counting 배열은 오름차순 상태이다. 즉, counting 배열의 값을 하나씩 줄이면서(숫자 개수만큼) 결과 배열에 배치하면 결과 배열도 오름차순 상태가 된다.
Ex)
array[0] = 7, counting[7] = 12
=> counting[7]--;
=> result[counting[7] - 1] = array[0];
counting 은 누적합이므로 0부터 시작하는 인덱스와 맞으려면 -1을 해야 한다.
다만 안정적으로 정렬하기 위해서는 array의 마지막 index 부터 순회하는 것이 좋다.
이런식으로 하면 result 배열은 array 배열의 정렬된 형태로 있게 된다.
이 과정 자체가 두 수를 비교하는 과정이 없기 때문에 빠른 배치가 가능하다. 다만 몇 가지 단점 또한 존재한다.
바로 counting 배열이라는 새로운 배열을 선언해주어야 한다는 점이다. 생각보다 이 단점이 꽤 클 수 있는데, array 안에 있는 max 값의 범위에 따라 counting 배열의 길이가 달라지게 된다. 예를 들어 10개의 원소를 정렬하고자 하는데, 수의 범위가 0~1억이라면 메모리가 매우 낭비된다.
즉, Counting Sort가 효율적인 상황에서 쓰려면 수열의 길이보다 수의 범위가 극단적으로 크면 메모리가 엄청 낭비될 수 있다는 것이다. 그렇기 때문에 각기 상황에 맞게 정렬 알고리즘을 써야 하는데, 퀵 정렬이나 병합 정렬 등이 선호되는 이유도 이에 있다.
(Quick Sort의 경우 시간복잡도 평균값이 O(nlongn)으로 빠른편이면서 배열도 하나만 사용하기 때문에 공간복잡도는 O(n)으로 시간과 메모리 둘 다 효율적이라는 점이다.)
🌿 구현
package sort;
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이 될 때까지 인덱스를 출력해주면 된다.
public class counting_sort {
public static void main(String[] args) {
int[] arr = new int[101]; // 수의 범위 : 0 ~ 100
for (int i = 0; i < 50; i++) { // 수열의 크기 : 50
arr[(int) (Math.random() * 101)]++; // 0 ~ 100
}
for(int i = 0; i < arr.length; i++) {
while(arr[i]-- > 0) { // arr 값이 0보타 클 경우
System.out.print(i + " ");
}
}
}
}백준에서 정렬 문제를 풀 때 시간 제한이 매우 빡빡한 경우에는 Arrays.sort()를 쓰더라도 시간 초과가 난다. 특히 최악의 경우 퀵 정렬이라도 시간이 O(n^2)이기 때문에 이를 노리고 저격 데이터가 있을 수 있다. 그럴 때, 이 방법을 쓰는 것도 좋다.
그러나 일반적인 상황이라면 단순 숫자가 아닌 대부분 객체를 갖고 정렬을 하게 된다. 어디까지나 Counting Sort는 특정 타입에 한정되어있기도 하고, 만약 입력되는 수의 개수는 적지만, 수의 범위가 매우 클 경우 심한 메모리 낭비와 더불어 자바에서는 1차원 배열 객체 하나의 크기는 최대 Integer.MAX_VALUE 미만으로만 가능하기 때문에 (배열의 경우 int값으로 색인하며 또한 대부분의 사용자의 heap 메모리가 하나의 배열을 8GB 만큼 큰 메모리를 확보하지 못한다.) 실생활에서는 거의 안 쓰인다. 그렇기 때문에 대부분 언어에서는 TimSort나 QuickSort를 쓰는 것이다.
Reference URL : https://st-lab.tistory.com/104
