[Java] Collections.sort () VS Arrays.sort()

Collections.sort()와 Arrays.sort()는 정렬할 때 많이 사용하는 2가지 메서드입니다.

두 메서드는 정렬을 어떤 방식으로 진행할까요?

Arrays.sort()

배열을 정렬할 때 사용합니다.

 

Arrays.sort() 내부구조

  /**
     * Sorts the specified array into ascending numerical order.
     *
     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
     * offers O(n log(n)) performance on many data sets that cause other
     * quicksorts to degrade to quadratic performance, and is typically
     * faster than traditional (one-pivot) Quicksort implementations.
     *
     * @param a the array to be sorted
     */
    public static void sort(int[] a) {
        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }

DualPivotQuicksort라는 알고리즘을 사용합니다.

O(n log(n)) 의 시간 복잡도를 가지며 pivot을 하나 사용하는 Quicksort 보다 빠르다고 합니다.

 

Collections.sort()

컬렉션(List, Set 등)을 정렬할 때 사용합니다.

삽입 정렬과 합병 정렬을 결합한 정렬입니다.

 

Collections.sort() 내부구조

public static <T extends Comparable<? super T>> void sort(List<T> list) {
        list.sort(null);
    }

Collections 클래스의 sort 메서드는 List <T> 타입을 가지는 list를 매개변수로 받아 list.sort(null); 메서드를 실행합니다.

 

한번 더 타고 내부로 들어가 보겠습니다.

/*
The implementation was adapted from Tim Peters's list sort for Python
(<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
TimSort</a>).  It uses techniques from Peter McIlroy's "Optimistic
Sorting and Information Theoretic Complexity", in Proceedings of the
Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
January 1993.
*/


@SuppressWarnings({"unchecked", "rawtypes"})
    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);
        }
    }

Tim Peters에 의해 구현되었기 때문에 TimeSort라고 불린다고 합니다.

내부적으로 Array로 변환하여 Arrays.sort()를 사용합니다.

 

Arrays.sort()를 타고 내부로 들어가 보겠습니다.

   public static <T> void sort(T[] a, Comparator<? super T> c) {
        if (c == null) {
            sort(a);
        } else {
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a, c);
            else
                TimSort.sort(a, 0, a.length, c, null, 0, 0);
        }
    }

Comparator가 null이면 sort(a)를 진행하고 Comparator가 존재한다면 legacyMergeSort 또는 TimSort를 사용하여 정렬을 진행합니다.

 

legacyMergeSort.userRequested란?

'-Djava.util.Arrays.useLegacyMergeSort=true' 자바 환경변수 설정을 통해 사용할 수 있습니다.

legacyMergeSort는 Deprecated 되어 있습니다.

즉, 일반적으로는 TimSort를 사용합니다.

 

 

 

Arrays.sort() vs Collections.sort()

	정렬 방식	시간 복잡도
Arrays.sort()	DualPivotQuicksort	평균 : O(nlog(n)) / 최악 : O(n^2)
Collections.sort()	TimeSort (삽입정렬과 합병정렬을 결합한 정렬)	평균, 최악 : O(nlog(n))

 

 

출처

https://yuja-kong.tistory.com/183

[Java] Arrays.sort()와 Collections.sort()의 시간복잡도 비교

https://d2.naver.com/helloworld/0315536

https://sabarada.tistory.com/138

[Java] Java의 정렬 알고리즘 - Arrays와 Collections

https://taes-k.github.io/2021/04/19/java-sort/

몰라도 되는 Java - sort 알고리즘