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);
        }