Counting Sort는 조금은 특이한 정렬 알고리즘이다.
정렬 알고리즘 중 유일하게 O(N)의 시간복잡도를 가지고 있다.
(정확히는 O(N+E) 이다. N : 인풋 데이터 수, E : 주어지는 데이터의 범위 ( 보통 0 ~ 최대값 ) )
따라서 코딩테스트에서 정렬 API로 정렬하지 못하는 데이터를 시간 내에 정렬할 수도 있음으로 알아두면 좋다!
또한 카운팅 정렬을 단순하게 구현하면 불안정 정렬로 구현될 수 있다.
안정 정렬로 구현하는 것이 바람직함으로 두 가지 방법 모두 알아보자!
1. 불안정 정렬 구현
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] nums = {0,4,1,4,1,2,4,1};
int N = nums.length;
int K = 4; // 최대값
int[] count = new int[K+1];
// 카운팅
for (int i = 0; i < N; i++) {
count[nums[i]]++;
}
// 정렬
int idx = 0;
for (int i = 0; i <= K; i++) {
for (int j = 0; j < count[i]; j++) {
nums[idx+j] = i;
}
idx += count[i];
}
System.out.println(Arrays.toString(nums));
}
}[0,1,1,1,2,4,4,4]
다만 불안정 정렬로 1번 idx에 있는 1이 2번 idx에 있는 1보다 더 뒤에 있던 값이 아닐 수 있다.
해당 문제는 2차원 배열이나 Class 변수와 같이 파라미터가 2개 이상인 데이터의 정렬에서 문제가 생길 수 있음으로 안정 정렬로 이를 개선하는 방법을 고민해보자.
2. 안정 정렬
그러면 어떻게 안정 정렬로 개선할 수 있을까?
누적합과 역순 탐색을 이용하면 되는데 카운팅 배열을 누적합하게 되면 ( 누적합 배열에 저장된 값- 1 ) 이 해당 idx의 마지막 값이 들어갈 위치이다!
예시로 살펴보자
주어진 배열은 아래와 같다
| 1 | 3 | 3 | 2 | 4 | 1 | 4 | 3 |
이를 카운팅 하고 누적합한 결과는 아래와 같다.
| 카운팅 배열 idx | 1 | 2 | 3 | 4 |
| 카운팅 | 2 | 1 | 3 | 2 |
| 누적합 | 2 | 3 (2+1) | 6 (2+1+3) | 8 |
정렬 결과는 아래와 같다
| idx | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 정렬 결과 | 1 | 1 | 2 | 3 | 3 | 3 | 4 | 4 |
정렬 결과에서 정렬 결과가 바뀌는 지점, 즉 어떠한 수가 마지막으로 나오는 위치를 자세히 보자.
앞에서 부터 순서대로 보면
1이 2개 있음으로 idx 1까지,
2는 1개 있음으로 1의 마지막 idx인 1에서 한 칸 뒤인 idx 2까지,
3은 3개 있음으로 2의 마지막 idx인 2에서 세 칸 뒤인 idx 5까지인 것을 알 수 있다. (4도 마찬가지이다)
이 결과를 보고 누적합 결과를 보면 누적합 값에서 1을 빼면 현재 숫자가 마지막으로 나오는 위치를 알려준다고 할 수 있다.
그러면 이를 어떻게 안정정렬에 확인할 수 있는가?
안정정렬은 만약 비교하는 파라미터의 값이 같다면 그 데이터는 기존 순서를 보장해야 한다.
따라서 같은 3이라도 원래 맨 뒤에 위치했던 3은 맨 뒤에 있어야 한다.
그런데.. 우리는 누적합 배열을 통해 어떠한 수가 마지막으로 나오는 위치를 알 수 있게 되었다!
따라서 원 배열을 뒤에서부터 탐색하여 해당 수의 마지막 위치에 넣어주면 되지 않을까?
다시 원 배열을 살펴보자
역순으로 탐색하기로 했으니, 원 배열의 마지막 값은 3이고, 3은 총 3개가 있다.
| 1 | 3 (1) | 3 (2) | 2 | 4 | 1 | 4 | 3 (3) |
우리가 보고 있는 마지막 3의 누적합 값은 6이다.
그 뜻은, 정렬 되었을 때 6-1 인 5번 idx 위치가 3의 마지막 위치라는 것이다
| 카운팅 배열 idx | 1 | 2 | 3 | 4 |
| 카운팅 | 2 | 1 | 3 | 2 |
| 누적합 | 2 | 3 | 6 | 8 |
따라서 해당 위치에 정렬할 수 있다.
| idx | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 정렬 결과 | 1 | 1 | 2 | 3 | 3 | 3 (3) | 4 | 4 |
마지막으로 3이 1개 정렬되었음으로 누적합 값을 1 감소시켜준다.
그러면 다음 3이 나온다면 해당 3은 4번 idx에 위치시키면 된다는 것을 알게 될 것이다!
| 카운팅 배열 idx | 1 | 2 | 3 | 4 |
| 카운팅 | 2 | 1 | 3 | 2 |
| 누적합 | 2 | 3 | 5 | 8 |
한 번만 더 보자! 다음 값은 4이다.
| 1 | 3 | 3 | 2 | 4 (1) | 1 | 4 (2) | 3 |
4의 누적합 값은 8임으로 정렬된 배열의 7번 idx에 마지막 4가 위치한다는 뜻이다.
| 카운팅 배열 idx | 1 | 2 | 3 | 4 |
| 카운팅 | 2 | 1 | 3 | 2 |
| 누적합 | 2 | 3 | 5 | 8 |
따라서 해당 위치에 정렬할 수 있다.
| idx | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 정렬 결과 | 1 | 1 | 2 | 3 | 3 | 3 | 4 | 4 (2) |
마지막으로 4가 1개 정렬되었음으로 누적합 값을 1 감소시켜준다.
| 카운팅 배열 idx | 1 | 2 | 3 | 4 |
| 카운팅 | 2 | 1 | 3 | 2 |
| 누적합 | 2 | 3 | 5 | 7 |
이 로직을 반복하면 안정정렬이 가능하다!
위 로직을 코드로 살펴보자
import java.util.Arrays;
public class CountingSort {
public static void main(String[] args) {
int[][] nums = {{0,1}, {1,4}, {4,3}, {5,2}, {2,4}, {3,3}, {3,2}, {3,1}, {1,5}};
int N = nums.length;
// 최대값을 구한다.
int max = Integer.MIN_VALUE;
for (int i = 0; i < N; i++) {
if (nums[i][0] > max) max = nums[i][0];
}
// 카운팅 배열을 만든다.
int[] count = new int[max + 1];
for (int i = 0; i < N; i++) {
count[nums[i][0]]++;
}
// 카운팅 배열을 누적합한다.
for (int i = 1; i <= max; i++) {
count[i] += count[i-1];
}
// 누적합 값의 위치는 해당 인덱스의 값을 가진 맨 뒤에 위치했던 데이터가 들어가는 위치보다 1칸 뒤의 값이다
// (예를 들어 index 2의 누적합이 6라면 실제 배열에서 index 5 위치에 마지막 2짜리 값이 들어갈 수 있다)
int[][] result = new int[N][2];
for (int i = N-1; i >= 0; i--) {
int n = nums[i][0];
result[--count[n]] = nums[i];
}
System.out.println(Arrays.deepToString(result));
}
}[[0, 1], [1, 4], [1, 5], [2, 4], [3, 3], [3, 2], [3, 1], [4, 3], [5, 2]]
3. 최소값 고려하기
카운팅 정렬에는 치명적인 단점이 있는데
최대값과 최소값의 범위가 크면 시간복잡도 (O(N+E) , E : 최대~최소값 범위) ,
공간복잡도 (최대값 + 1 크기의 카운팅 배열 필요) 가 오히려 높게 올라갈 수 있다.
만약 문제에서 최대값이 크나 최소값도 커서 주어진 값의 범위 자체는 좁은 경우에는
카운팅 배열의 범위를 좁히는 방법으로 개선해 볼 수 있다.
아래 코드 예시를 보자.
2번 코드에서 주어지는 인풋값이 모두 1000씩 증가했음으로 6개 짜리 int 배열에서 1006개 짜리 int 배열이 필요했으나
최소값을 같이 고려하면 똑같이 6개짜리 int 배열로 정렬할 수 있다.
어려운 내용이 아니니 코드만 살짝 봐보자
import java.util.Arrays;
public class CountingSort {
public static void main(String[] args) {
int[][] nums = {{1000,1001}, {1001,1004}, {1004,1003}, {1005,1002}, {1002,1004}, {1003,1003}, {1003,1002}, {1003,1001}, {1001,1005}};
int N = nums.length;
// 최대값 & 최소값을 구한다.
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
if (nums[i][0] > max) max = nums[i][0];
if (nums[i][0] < min) min = nums[i][0];
}
// 카운팅 배열을 만든다. 최소값이 0에 가도록 idx를 조정해준다
int[] count = new int[max - min +1];
for (int i = 0; i < N; i++) {
count[nums[i][0] - min]++;
}
for (int i = 1; i <= max-min; i++) {
count[i] += count[i-1];
}
int[][] result = new int[N][2];
for (int i = N-1; i >= 0; i--) {
int n = nums[i][0] - min;
result[--count[n]] = nums[i];
}
System.out.println(Arrays.deepToString(result));
}
}[[1000, 1001], [1001, 1004], [1001, 1005], [1002, 1004], [1003, 1003], [1003, 1002], [1003, 1001], [1004, 1003], [1005, 1002]]'Java' 카테고리의 다른 글
| [Optional] Optional 사용법과 프로젝트 적용 예시 (with 모던 자바 인 액션) (1) | 2024.02.11 |
|---|