Sort : Arrays.sort() vs Collections.sort() & 배열 다중 정렬 및 출력
Arrays.sort() vs Collections.sort 두개는 사용하는 정렬이 다르다. .... ?
정답 )
Collections.sort() 는 List 객체를 object 로 변환해서 Arrays.sort() 를 실행한다.
Arrays.sort() 는 primitive type 의 경우 DualQuickSort , 아닌 경우 Merge Sort 를 변형시킨 TimSort 를 사용한다.
QuickSort() 의 경우는 안정성을 보장하지 않는다 . 1,4,3,3,5,3 일때 , 중복되는 숫자의 순서가 바뀔 수가 있다.
- 원시 타입의 값들은 배열의 중복되는 값들의 순서가 중요하지 않는 경우이니 , 평균속도가 빠른 QuickSort 를 이용하고
- 안정성이 보장이 되어야 하는 "객체" , 중복값을 가지지만 식별자가 다른 , 객체들의 정렬에서는 MergeSort() 계열인 Tim sort 를 사용하게 된다.
즉 Arrays.sort() , Collections.sort() 는 사용하는 정렬이 다른 것이 아니라 , Arrays.sort 가 두가지의 방식의 정렬 알고리즘을 사용하고, Collections.sort() 는 Arrays.sort() 의 오버라이드 된 메서드중 하나를 사용한다.
---------------------------------------------------------------------------------------------------------------------
추가 설명 )
타입 부터 보자.
Arrays.sort() : 배열을 정렬하기 위해 사용된다.
Collections.sort() : List 와 같은 컬랙션 객체를 정렬하기 위해 사용이된다.
- 배열 정렬을 학습할때 배우는 "안정성"을 전부 확인하자.
Arrays.sort() : 주어진 데이터에 따라 다른 정렬을 사용한다.
- int[] , double[] 과 같은 경우 퀵 소트를 변형한 DoublePivotQuickSort 알고리즘을 사용한다 .
모든 데이터의 대한 : O(N log N)
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, 0, a.length);
}
- 객체/참조의 배열 : String[] 와 같은 경우 TimSort를 사용한다라고 보면된다 .
-> 단순 병합정렬이 아닌 부분 병합정렬 + selectionSort 이다.
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}
public static <T> void sort(T[] a, Comparator<? super T> c) {
if (c == null) {
sort(a, fromIndex, toIndex);
} else {
rangeCheck(a.length, fromIndex, toIndex);
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, fromIndex, toIndex, c);
else
TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
}
}
Collections.sort()
기본) 내부적으로 list.sort() 를 사용한다.
public static <T extends Comparable<? super T>> void sort(List<T> list) {
list.sort(null);
}Compartator 를 던져주면 내부적으로 다음 함수를 사용한다.
public static <T> void sort(List<T> list, Comparator<? super T> c) {
list.sort(c);
}
list.sort()
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}2. 내부적으로 Arrays.sort() 를 사용한다.
정리 )
Collections.sort() 는 List 객체를 object 로 변환해서 Arrays.sort() 를 실행한다.
Arrays.sort() 는 primitive type 의 경우 DualQuickSort , 아닌 경우 TimSort 를 사용하며 안정성이 관련이 있다.
다중 배열 출력
2 중 배열을 단순 Arrays.toString 을 할시 객체의 주소값이 보인다.
2중 배열의 출력은 다음과 같이 해주자. : Arrays.deepTiString(arr) ;
System.out.println(Arrays.deepToString(given));
다중 배열 정렬
나이 , 점수가 주어진 배열에서 , 나이로 오름차순으로 정렬 후 , 동점일 경우 점수를 기준으로 오름 차순으로 정렬하는 방식은 다음과 같다.
Java 8 이상의 버전에서 지원하는 람다 함수를 활용해 주자.
이때 return a - b , 는 음수인 경우 : b > a 이니, a 가 b 보다 앞에 있어야 오름 차순이 된다.
@Test
void sort_test() {
int[][] a ={{12,31},{41,13},{21,1},{1,21},{1,22},{22,11},{1,23}};
// 순서 : 나이 점수
sort_test(a);
}
private void sort_test(int[][] given ){
// 나이 오름 , 점수 내림 순으로 정렬
Arrays.sort(given,(a,b)->{
if(a[0] != b[0]) return a[0] - b[0];
return b[1] - a[1];
}
);
System.out.println(Arrays.deepToString(given));
}
List<List<Integer> , 이중 리스트 정렬 방식
@Test
void collection_sort_test(){
List<List<Integer>> arr = new ArrayList<>();
arr.add(Arrays.asList(1,2));
arr.add(Arrays.asList(4,2));
arr.add(Arrays.asList(12,2));
arr.add(Arrays.asList(1,24));
arr.add(Arrays.asList(11,2));
arr.add(Arrays.asList(1,21));
System.out.println(arr);
arr.sort(arr,(a,b)->{
if(a.get(0) == b.get(0)) return b.get(1) - a.get(1);
return a.get(0)- b.get(0);
});
System.out.println(arr);
}