[java] Collections.sort가 빠른 정렬 대신 병합 정렬을 사용하는 이유는 무엇입니까?

JAVA / 글쓴이

우리는 빠른 정렬이 가장 빠른 정렬 알고리즘이라는 것을 알고 있습니다.

JDK6 collections.sort는 빠른 정렬 대신 병합 정렬 알고리즘을 사용합니다. 그러나 Arrays.sort는 빠른 정렬 알고리즘을 사용합니다.

Collections.sort가 빠른 정렬 대신 병합 정렬을 사용하는 이유는 무엇입니까?

답변

Josh Bloch의 가능성이 높음 § :

이 방법을 작성 했으므로 대답 할 자격이 있다고 생각합니다. 최상의 정렬 알고리즘이 하나도 없다는 것은 사실입니다. QuickSort는 mergesort와 비교할 때 두 가지 주요 결함이 있습니다.

  1. 안정적이지 않습니다 (파시 팔이 언급했듯이).

  2. n log n 성능을 보장 하지 않습니다 . 병리학 적 입력에 대한 2 차 성능으로 저하 될 수 있습니다.

(가치) 평등과 구별되는 동일성 개념이 없기 때문에 안정성은 원시 유형의 경우 문제가되지 않습니다. 그리고 2 차 동작의 가능성은 실제로 Bentely와 McIlroy의 구현 (또는 이후 Dual Pivot Quicksort )에서는 문제가되지 않는 것으로 간주되었으므로 이러한 QuickSort 변형이 기본 정렬에 사용되었습니다.

안정성은 임의의 개체를 정렬 할 때 큰 문제입니다. 예를 들어 전자 메일 메시지를 나타내는 개체가 있고 먼저 날짜별로 정렬 한 다음 보낸 사람별로 정렬한다고 가정합니다. 각 발신자 내에서 날짜별로 정렬 될 것으로 예상하지만 정렬이 안정적인 경우에만 해당됩니다. 이것이 우리가 객체 참조를 정렬하기 위해 안정적인 정렬 (Merge Sort)을 제공하기로 선택한 이유입니다. (기술적으로 말하면 여러 순차 안정적인 정렬은 정렬의 역순으로 키에 사전 식 순서를 지정합니다. 최종 정렬은 가장 중요한 하위 키를 결정합니다.)

Merge Sort 가 입력에 관계없이 n log n (시간) 성능을 보장 한다는 것은 좋은 부수적 인 이점입니다 . 물론 단점이 있습니다. 빠른 정렬은 “인플레 이스”정렬입니다. (호출 스택을 유지하기 위해) log n 개의 외부 공간 만 필요합니다. 반면 병합, 정렬에는 O (n) 외부 공간이 필요합니다. TimSort 변형 (Java SE 6에 도입 됨)은 입력 배열이 거의 정렬 된 경우 상당히 적은 공간 (O (k))을 필요로합니다.

또한 다음 사항 이 관련됩니다.

java.util.Arrays.sort 및 java.util.Collections.sort가 객체 참조를 정렬하기 위해 (간접적으로) 사용하는 알고리즘은 “수정 된 병합 정렬 (하위 하위 목록의 최상위 요소가 다음보다 작 으면 병합이 생략 됨)입니다. 상위 하위 목록에서 가장 낮은 요소). ” O (n log n) 성능을 보장하고 O (n) 추가 공간을 필요로하는 상당히 빠르고 안정적인 정렬입니다. 그 당시에는 (Joshua Bloch가 1997 년에 썼습니다) 좋은 선택 이었지만 오늘날에는 훨씬 더 잘할 수 있습니다.

2003 년부터 Python의 목록 정렬은 timsort (이를 작성한 Tim Peters의 뒤를 따름)라는 알고리즘을 사용했습니다. 부분적으로 정렬 된 배열에서 실행할 때 n log (n) 비교가 훨씬 더 적게 필요한 안정적이고 적응 적이며 반복적 인 병합 정렬이며, 무작위 배열에서 실행될 때 기존 병합 정렬과 유사한 성능을 제공합니다. 모든 적절한 병합 정렬과 마찬가지로 timsort는 안정적이며 O (n log n) 시간 (최악의 경우)에 실행됩니다. 최악의 경우, timsort는 n / 2 개의 객체 참조를위한 임시 저장 공간이 필요합니다. 가장 좋은 경우에는 일정한 공간이 조금만 필요합니다. 이것은 항상 n 개의 객체 참조를위한 추가 공간이 필요하고 거의 정렬 된 목록에서만 n log n을 능가하는 현재 구현과 대조됩니다.

Timsort는 http://svn.python.org/projects/python/trunk/Objects/listsort.txt 에 자세히 설명되어 있습니다
.

Tim Peters의 원래 구현은 C로 작성되었습니다. Joshua Bloch는이를 C에서 Java로 포팅하고 최종 테스트, 벤치마킹 및 결과 코드를 광범위하게 조정했습니다. 결과 코드는 java.util.Arrays.sort의 드롭 인 대체입니다. 순서가 높은 데이터에서이 코드는 현재 구현 (HotSpot 서버 VM에서)보다 최대 25 배 빠르게 실행될 수 있습니다. 임의의 데이터에서 이전 구현과 새 구현의 속도는 비슷합니다. 매우 짧은 목록의 경우 새로운 구현은 임의 데이터에서도 이전 구현보다 훨씬 빠릅니다 (불필요한 데이터 복사를 방지하기 때문입니다).

또한 Java 7에서 메서드 배열에 Tim Sort를 사용하고 있습니까?를 참조하십시오 . .

하나의 “최선의”선택은 없습니다. 다른 많은 것들과 마찬가지로 트레이드 오프에 관한 것입니다.

답변