[Java] 정렬
방법 1) Arrays.sort()
int[] arr = new int[5];
Arrays.sort(arr);
// => arr 오름차순 정렬※ 시간 복잡도 : 평균 O(nlog n) / 최악 O(n^2)
Sort 메소드 심화
sort 메소드는 두 가지 인자를 받을 수 있다.
public static <T> void sort(T[] a, Comparator<? super T> c)
1. 제너릭 타입 객체배열(T[]) -> 클래스, 오브젝트, 자료형 등 어떤 타입이든 상관 없이 배열의 형태로 받을 수 있다.
ex) int[] 형 배열을 쓸 경우 T는 int 로 결정.
2. <? super T> 는 상속관계에 있는 타입만 자료형으로 받겠다는 의미. Comparator 는 람다식으로 표현가능.
compare 메소드를 오버라이딩 하여 compare 메소드 안에 자신만의 비교 방법(우선순위 판단)을 구현함
ex) 백준 11650문제 (X Y 좌표 비교하여 오름차순 정렬)
int[][] arr = new int[N][2];
Arrays.sort(arr, (e1, e2) -> {
if(e1[0] == e2[0])
return e1[1] - e2[1];
else
return e1[0] - e2[0];
});
방법 2) Collections.sort()
Collections.sort() 는 Timsort 이다. (합병 및 삽입정렬 사용) => hybrid sorting algorithm
- 합병정렬(Merge Sort) : 최선, 최악 둘다 O(nlog n)
- 삽입정렬(Insertion Sort) : 최선 O(n), 최악 O(n^2)
따라서 Timsort 는 시간복잡도 O(n) ~ O(nlog n) 를 보장한다.
=> List 계열(ArrayList, LinkedList 등 .. ) 의 자료구조를 사용해야 함.
※ 단점 : List 계열 자료구조를 사용하다 보니 메모리 공간을 많이 차지함.
방법 3) Counting Sort
카운팅 정렬의 시간 복잡도 : O(n)
퀵 정렬(Quick Sort), 힙 정렬(Heap Sort), 합병 정렬(Merge Sort) 등의 평균 시간 복잡도 : O(nlog n)
정렬 방법
아래와 같은 배열이 있다고 가정해보자.
int[] arr = {7, 2, 3, 5, 7, 1, 4, 6, 7, 5, 0, 1}
| 7 | 2 | 3 | 5 | 7 | 1 | 4 | 6 | 7 | 5 | 0 | 1 |
- 과정 1
arr 을 한번 순회하면서 각 값이 나올 때 마다 해당 값을 index 로 하는 새로운 배열의 값을 1 증가.
arr[0] = 7 이므로 counting[7] 값을 1 증가,
arr[1] = 2 이므로 counting[2] 값을 1 증가,
...
arr[12] = 1 이므로 counting[1] 값을 1 증가.
위 과정을 거치면 아래와 같은 counting 배열이 나온다.
| 1 | 2 | 1 | 1 | 1 | 2 | 1 | 3 |
- 과정 2
counting 배열의 값을 누적 합으로 변환 시킨다.
| 1 | 2 | 1 | 1 | 1 | 2 | 1 | 3 |
+ ↓
| 1 | 3 | 1 | 1 | 1 | 2 | 1 | 3 |
| 1 | 3 | 1 | 1 | 1 | 2 | 1 | 3 |
+ ↓
| 1 | 3 | 4 | 1 | 1 | 2 | 1 | 3 |
위 과정을 반복하면 아래와 같은 새로운 counting 배열을 만들 수 있다.
| 1 | 3 | 4 | 5 | 6 | 8 | 9 | 12 |
- 과정 3
counting 배열의 각 값은 (시작점 -1) 을 알려준다. 즉, 해당 값에 대응되는 위치에 배정하면 된다.
arr[0] = 7 이고, counting[7] = 12 이다. 여기서 counting[7] 의 값에 1을 뺀 값인 11 이 새로운 배열의 인덱스 11에 위치하게 된다.
다만 안정적으로 정렬하기 위해서는 arr 의 마지막 index 부터 순회하는 것이 좋다.
arr[11] = 1,
counting[1] = 3 (-1)
result[2] = 1
[반복 1]
<arr 배열>
| 7 | 2 | 3 | 5 | 7 | 1 | 4 | 6 | 7 | 5 | 0 | 1 |
<counting 배열>
| 1 | 3 (-1) | 4 | 5 | 6 | 8 | 9 | 12 |
↓
| 1 | 2 | 4 | 5 | 6 | 8 | 9 | 12 |
<result 배열> result[2] 에 위치
| 1 |
[반복 2]
<arr 배열>
| 7 | 2 | 3 | 5 | 7 | 1 | 4 | 6 | 7 | 5 | 0 | 1 |
<counting 배열>
| 1 (-1) | 2 | 4 | 5 | 6 | 8 | 9 | 12 |
↓
| 0 | 2 | 4 | 5 | 6 | 8 | 9 | 12 |
<result 배열> result[0] 에 위치
| 0 | 1 |
위 과정을 반복하면 아래와 같은 정렬된 result 배열을 얻을 수 있다.
| 0 | 1 | 1 | 2 | 3 | 4 | 5 | 5 | 6 | 7 | 7 | 7 |
※ 단점 : arr 안에 있는 max 값의 범위에 따라 counting 배열의 길이가 달라짐.
-> 메모리 공간이 낭비될 수 있음
코드
int[] arr = new int[100];
int[] counting = new int[31]; // 수의 범위 (0~31)
int[] result = new int[100];
for(int i=0; i<arr.length; i++)
arr[i] = (int)(Math.random()*31); // 0~30
// 과정 1
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
for(int i=arr.length-1; i>=0; i--) {
int value = arr[i];
counting[value]--;
result[counting[value]] = value;
}