Java의 Arrays.sort 메소드가 다른 유형에 대해 두 가지 다른 정렬 알고리즘을 사용하는 이유는 무엇입니까?

Java의 Arrays.sort 메소드가 다른 유형에 대해 두 가지 다른 정렬 알고리즘을 사용하는 이유는 무엇입니까?

---

Java 6의 Arrays.sort방법은 기본 배열에 Quicksort를 사용하고 객체 배열에 병합 정렬을 사용합니다. 대부분의 경우 Quicksort가 병합 정렬보다 빠르며 메모리 비용이 적게 든다고 생각합니다. 내 실험은 두 알고리즘이 모두 O (n log (n))이지만이를 지원합니다. 그렇다면 왜 다른 유형에 다른 알고리즘이 사용됩니까?

---

가장 가능성이 높은 이유 : 퀵 정렬이 안정적 이지 않습니다 . 즉, 동일한 항목이 정렬 중에 상대 위치를 변경할 수 있습니다. 무엇보다도 이것은 이미 정렬 된 배열을 정렬하는 경우 변경되지 않을 수 있음을 의미합니다.

기본 유형에는 ID가 없기 때문에 (동일한 값을 가진 두 개의 정수를 구별 할 방법이 없음) 이것은 중요하지 않습니다. 그러나 참조 유형의 경우 일부 응용 프로그램에서 문제가 발생할 수 있습니다. 따라서 안정적인 병합 정렬이 사용됩니다.

OTOH, 기본 유형에 대해 (보장 된 n * log (n)) 안정적인 병합 정렬을 사용하지 않는 이유는 배열의 복제본을 만들어야하기 때문일 수 있습니다. 참조 된 객체가 일반적으로 참조 배열보다 훨씬 더 많은 메모리를 차지하는 참조 유형의 경우 일반적으로 중요하지 않습니다. 그러나 원시 유형의 경우 배열을 완전히 복제하면 메모리 사용량이 두 배가됩니다.

---

에 인용 된 자바 7 API 문서에 따르면 이 답변 , Arrays#Sort()객체 배열 지금 사용 TimSort 머지 소트과 삽입 정렬의 하이브리드입니다. 반면, Arrays#sort()기본 배열의 경우 이제 Dual-Pivot QuickSort를 사용 합니다. 이러한 변경 사항은 Java SE 7부터 구현되었습니다.

---

내가 생각할 수있는 한 가지 이유는 quicksort가 최악의 경우 O ( n ^ 2 ) 의 시간 복잡도를 갖는 반면 mergesort는 최악의 경우 O ( n log n )의 시간을 유지 한다는 것입니다 . 객체 배열의 경우 퀵 정렬이 최악의 경우 인 중복 객체 참조가 여러 개있을 것으로 예상됩니다.

다양한 알고리즘에 대한 적절한 시각적 비교 가 있으며 다른 알고리즘에 대한 맨 오른쪽 그래프에 특히주의하십시오.

---

저는 알고리즘에 대한 Coursera 수업을 들었고 Bob Sedgewick 교수의 강의 중 하나에서 Java 시스템 정렬에 대한 평가를 언급했습니다.

"프로그래머가 객체를 사용하는 경우 공간은 매우 중요한 고려 사항이 아니며 병합 정렬에 사용되는 추가 공간은 문제가 아닐 수 있습니다. 프로그래머가 기본 유형을 사용하는 경우 성능이 가장 중요한 요소이므로 사용할 수 있습니다. 빠른 정렬. "

---

Java의 Arrays.sort방법은 빠른 정렬, 삽입 정렬 및 병합 정렬을 사용합니다. OpenJDK 코드에 구현 된 단일 및 이중 피벗 퀵소트도 있습니다. 가장 빠른 정렬 알고리즘은 상황에 따라 다르며 승자는 작은 배열에 대한 삽입 정렬 (현재 선택한 47 개), 대부분 정렬 된 배열에 대한 병합 정렬, 나머지 배열에 대한 빠른 정렬이므로 Java의 Array.sort ()는 최상의 알고리즘을 선택하려고합니다. 해당 기준에 따라 적용됩니다.

---

java.util.Arrays 는 Comparable 을 구현 하거나 Comparator를 사용하는 객체에 대해 int 및 mergesort 와 같은 기본 유형에 대해 quicksort 를 사용합니다 . 두 가지 다른 방법을 사용하는 아이디어는 프로그래머가 객체를 사용하는 경우 공간이 매우 중요한 고려 사항이 아니므로 병합 정렬에 사용되는 추가 공간 이 문제가되지 않을 수 있고 프로그래머가 기본 유형을 사용하는 경우 성능이 가장 중요한 것일 수 있으므로 사용하십시오 퀵 .

예 : 이것은 정렬 안정성이 중요한 경우의 예입니다.

그렇기 때문에 안정적인 정렬이 객체 유형, 특히 정렬 키보다 더 많은 데이터가있는 변경 가능한 객체 유형 및 객체 유형에 대해 의미가 있으며 mergesort가 그러한 정렬입니다. 그러나 원시 유형의 경우 안정성은 관련성이 없을뿐만 아니라 무의미합니다.

출처 : 정보

참고 URL : https://stackoverflow.com/questions/3707190/why-does-javas-arrays-sort-method-use-two-different-sorting-algorithms-for-diff