[java] Collections.sort는 Mergesort를 사용하지만 Arrays.sort는 사용하지 않는 이유는 무엇입니까?

Program / 글쓴이

JDK-8 (x64)을 사용하고 있습니다. 들어 Arrays.sort(프리미티브) 나는 자바 문서에 다음과 발견 :

정렬 알고리즘은 Vladimir Yaroslavskiy, Jon Bentley, Joshua Bloch 의 Dual-Pivot Quicksort입니다.

들어 Collections.sort(객체) 나는이 “Timsort”를 발견 :

이 구현은 안정적이고 적응 적이며 반복적 인 mergesort입니다 .이 구현 은 지정된 목록을 배열로 덤프하고 배열을 정렬 하며 목록을 반복 하여 배열 의 해당 위치에서 각 요소를 재설정합니다.

Collections.sort어레이를 사용하는 경우 Arrays.sort듀얼 피벗 QuickSort를 호출 하거나 사용 하지 않는 이유는 무엇입니까? Mergesort를 사용하는 이유는 무엇 입니까?

답변

API는 Quicksort 가 제공하지 않는 안정적인 정렬을 보장 합니다. 그러나 기본 값 을 자연 순서로 정렬 할 때 기본 값에는 동일성이 없기 때문에 차이를 느끼지 못할 것입니다. 따라서 Quicksort 는 기본 배열에 사용할 수 있으며 더 효율적인 것으로 간주 될 때 사용됩니다 ¹ .

객체의 경우 equals구현 또는 제공된 항목 에 따라 동일하다고 간주되는 다른 ID를 가진 객체 Comparator의 순서 가 변경 될 때 알 수 있습니다 . 따라서 Quicksort 는 옵션이 아닙니다. 따라서 MergeSort 의 변형 이 사용되며 현재 Java 버전은 TimSort를 사용 합니다 . 이는 Arrays.sort및 에 모두 적용 Collections.sort되지만 Java 8에서는 List자체가 정렬 알고리즘을 재정의 할 수 있습니다.

¹ Quicksort 의 효율성 이점은 제자리에서 수행 할 때 필요한 메모리가 적다는 것입니다. 그러나 극적으로 최악의 경우 성능을 가지고 있으며 TimSort 가 수행 하는 어레이에서 사전 정렬 된 데이터 실행을 악용 할 수 없습니다 .

따라서 정렬 알고리즘은 현재 잘못 명명 된 class를 유지하면서 버전마다 재 작업되었습니다 DualPivotQuicksort. 또한 문서는 필요하지 않을 때 사양에서 내부적으로 사용되는 알고리즘의 이름을 지정하는 것이 일반적으로 나쁜 생각이라는 것을 보여주지 못했습니다.

현재 상황 (Java 8 ~ Java 11 포함)은 다음과 같습니다.

  • 일반적으로 기본 배열의 정렬 방법은 특정 상황에서만 Quicksort 를 사용 합니다. 더 큰 어레이의 경우 TimSort 처럼 미리 정렬 된 데이터의 실행을 먼저 식별하고 실행 횟수가 특정 임계 값을 초과하지 않을 때 병합합니다. 그렇지 않으면 Quicksort로 폴백 되지만 작은 범위에 대한 삽입 정렬 로 폴백되는 구현이 포함되어 작은 배열뿐만 아니라 빠른 정렬의 재귀에도 영향을줍니다.
  • sort(char[],…)및 sort(short[],…)다른 특별한 경우를 추가, 사용하는 일종의 계산 배열 길이가 특정 임계 값을 초과에 대한
  • 마찬가지로 Counting sortsort(byte[],…) 를 사용 하지만 Quicksort를 사용하지 않기 때문에 문서와 가장 큰 대조를 이루는 임계 값이 훨씬 더 작습니다 . 작은 배열 에는 삽입 정렬 만 사용 하고 그렇지 않으면 계수 정렬 만 사용합니다 .sort(byte[],…)

답변

문서에 대해서는 모르지만 java.util.Collections#sortJava 8 (HotSpot) 의 구현 은 다음과 같습니다.

@SuppressWarnings({"unchecked", "rawtypes"})
public static <T> void sort(List<T> list, Comparator<? super T> c) {
    list.sort(c);
}

그리고이 List#sort구현이 있습니다.

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

따라서 결국 에는 장면 뒤에서 (객체 요소의) Collections#sort사용 Arrays#sort합니다. 이 구현은 병합 정렬 또는 팀 정렬을 사용합니다.

답변

Javadoc에 따르면 기본 배열 만 Quicksort를 사용하여 정렬됩니다. 객체 배열도 병합 정렬로 정렬됩니다.

따라서 Collections.sort는 Objects에 대해 Arrays.sort와 동일한 정렬 알고리즘을 사용하는 것 같습니다.

또 다른 질문은 왜 객체 배열보다 원시 배열에 다른 정렬 알고리즘이 사용되는 것입니까?

답변

많은 답변에서 언급했듯이.

Quicksort는 안정성이 필요하지 않기 때문에 Arrays.sort에서 기본 컬렉션을 정렬하는 데 사용됩니다 (정렬에서 두 개의 동일한 int가 교체되었는지 알거나 신경 쓰지 않습니다).

MergeSort 또는 더 구체적으로 Timsort는 Arrays.sort에서 개체 컬렉션을 정렬하는 데 사용됩니다. 안정성이 필요합니다. Quicksort는 안정성을 제공하지 않지만 Timsort는 제공합니다.

Collections.sort는 Arrays.sort에 위임하므로 MergeSort를 참조하는 javadoc을 볼 수 있습니다.

답변

빠른 정렬에는 병합 정렬과 관련하여 두 가지 주요 단점이 있습니다.

  • 원시적이지 않은 경우 안정적이지 않습니다.
  • n log n 성능을 보장하지 않습니다.

(가치) 평등과 구별되는 동일성 개념이 없기 때문에 안정성은 원시 유형의 경우 문제가되지 않습니다.

안정성은 임의의 개체를 정렬 할 때 큰 문제입니다. Merge Sort가 입력에 관계없이 n log n (시간) 성능을 보장한다는 것은 좋은 부수적 인 이점입니다. 이것이 개체 참조를 정렬하기 위해 안정적인 정렬 (Merge Sort)을 제공하기 위해 병합 정렬을 선택한 이유입니다.

답변