컬렉션의 이유정렬은 빠른 정렬 대신 병합 정렬을 사용합니까?

컬렉션의 이유정렬은 빠른 정렬 대신 병합 정렬을 사용합니까?

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

JDK6collections.sort에서는 퀵소트 대신 머지소트 알고리즘을 사용합니다.알고리즘을 사용합니다.

수집의 이유는 무엇입니까?정렬은 빠른 정렬 대신 병합 정렬을 사용합니까?

Josh Bloch의 가능성이 매우 높다 »:

내가 이 방법들을 썼으니 대답할 자격이 있을 것 같아.최적의 정렬 알고리즘이 하나뿐인 것은 사실입니다.QuickSort에는 MargeSort에 비해 두 가지 주요 결함이 있습니다.

1. (파시팔이 지적한 바와 같이) 불안정합니다.

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

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

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

Merge Sort가 입력에 관계없이 n개의 로그 n(시간) 성능을 보증하는 것은 좋은 이점입니다.물론 단점도 있습니다.빠른 정렬은 "설치" 정렬입니다.로그 n개의 외부 공간만 요구됩니다(콜 스택을 유지하기 위해서).반면 병합, 정렬에는 O(n) 외부 공간이 필요합니다.TimSort 배리언트(Java SE 6에서 도입)는 입력 배열이 거의 정렬된 경우 필요한 공간(O(k))이 상당히 줄어듭니다.

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

java.util에서 사용되는 알고리즘.arrays.sort 및 (간접적으로) java.util로 지정합니다.컬렉션sort to sort object references는 "merge mergesort(하위 서브리스트의 상위 요소가 상위 서브리스트의 하위 요소보다 작을 경우 병합이 생략됨)"입니다.이것은 O(n log n)의 성능을 보장하고 O(n)의 추가 공간을 필요로 하는 상당히 빠른 안정적인 정렬입니다.1997년 Joshua Bloch에 의해 쓰여진 이 책은 당시에는 훌륭한 선택이었지만, 오늘날에는 훨씬 더 잘 할 수 있다.

2003년 이후 Python의 목록 정렬은 timsort로 알려진 알고리즘을 사용해 왔습니다(이 알고리즘을 작성한 Tim Peters의 이름을 따왔다.안정적이고 적응성이 뛰어난 반복적인 MargeSort로, 부분적으로 정렬된 어레이에서 실행할 경우 n개의 로그(n)보다 훨씬 적은 로그(n)를 비교해야 하며 랜덤 어레이에서 실행할 경우 기존 MargeSort와 동등한 성능을 제공합니다.모든 적절한 병합과 마찬가지로 팀소트는 안정적이며 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 사용 여부도 참조하십시오.정렬?

"최선의" 선택은 단 한 가지 않습니다.다른 많은 것들과 마찬가지로, 그것은 트레이드오프에 관한 것입니다.

언급URL : https://stackoverflow.com/questions/15154158/why-collections-sort-uses-merge-sort-instead-of-quicksort