왜 Java 어레이인가?정렬 방법은 두 가지 다른 유형의 정렬 알고리즘을 사용합니까?

왜 Java 어레이인가?정렬 방법은 두 가지 다른 유형의 정렬 알고리즘을 사용합니까?

의 © 6Arrays.sort메서드는 기본 배열에 QuickSort를 사용하고 개체 배열에 대해 병합 정렬을 사용합니다.퀵소트 마지소트두 알고리즘 모두 O(n log(n)이지만 내 실험은 그것을 지원한다.그럼 왜 다른 알고리즘이 다른 타입에 사용되는 걸까요?

가장 가능성이 높은 이유: QuickSort가 안정적이지 않습니다.즉, 동일한 엔트리가 정렬 중에 상대적인 위치를 변경할 수 있습니다.다른 이유 중에서도 이미 정렬된 어레이를 정렬하면 변경되지 않을 수 있습니다.

원시 유형에는 ID가 없기 때문에(같은 값을 가진2개의 int를 구별할 수 있는 방법은 없습니다), 이것은 문제가 되지 않습니다.그러나 참조 유형의 경우 일부 애플리케이션에서 문제가 발생할 수 있습니다.따라서 이러한 경우 안정적인 병합 정렬이 사용됩니다.

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

이 답변에서 인용된 Java 7 API 문서에 따르면,Arrays#Sort()오브젝트 어레이의 경우 MergeSort와 InsertionSort의 하이브리드인 TimSort를 사용하게 되었습니다.반면에,Arrays#sort()이제 듀얼피봇 QuickSort를 사용할 수 있게 되었습니다.이러한 변경은 Java SE 7부터 구현되었습니다.

생각할 수 있는 이유 중 하나는 QuickSort의 시간 복잡도가 O(n^2)인 반면 mergesort의 시간 복잡도는 O(n log n)인 최악의 시간을 유지하는 것입니다.오브젝트 배열의 경우 중복되는 오브젝트 참조가 여러 개 있을 것으로 예상되며, 이는 QuickSort가 최악의 경우 중 하나입니다.

다양한 알고리즘의 시각적 비교가 가능합니다. 특히 다양한 알고리즘의 오른쪽 그래프에 유의하십시오.

저는 알고리즘에 관한 Coursera 수업을 듣고 있었습니다.또한 Java 시스템 분류에 대한 평가에 대해 Bob Sedgewick 교수님의 강의 중 하나였습니다.

"프로그래머가 객체를 사용하고 있다면 공간은 매우 중요한 고려사항이 아닐 수 있으며, 머지 정렬에 사용되는 여분의 공간은 문제가 없을 수 있습니다.프로그래머가 원시형을 사용하고 있다면 퍼포먼스가 가장 중요하기 때문에 빠른 정렬을 사용합니다.

java.displaces를 클릭합니다.어레이는 Comparible을 구현하거나 Comparator를 사용하는 개체의 int 및 mergesort와 같은 원시 유형에 빠른 정렬을 사용합니다.두 가지 다른 방법을 사용하는 것은 프로그래머가 객체를 사용하는 경우 공간이 매우 중요하지 않을 수 있기 때문에 머지소트가 사용하는 여분의 공간은 문제가 되지 않을 수 있으며 프로그래머가 원시 유형을 사용하는 경우 성능이 가장 중요하므로 빠른 정렬을 사용할 수 있습니다.

예:이것은 안정성 문제를 정렬하는 경우의 예입니다.

따라서 안정적인 정렬은 객체 유형, 특히 정렬 키보다 더 많은 데이터를 가진 가변 객체 유형 및 객체 유형에 적합하며, 병합 정렬은 이와 같은 정렬입니다.그러나 원시 유형에서 안정성은 무관한 것만은 아닙니다.의미가 없어요.

출처: 정보

자바어Arrays.sort메서드는 QuickSort, 삽입 정렬 및 병합을 사용합니다.OpenJDK 코드에는 싱글 피벗 퀵소트와 듀얼 피벗 퀵소트가 모두 실장되어 있습니다.가장 빠른 정렬 알고리즘은 상황에 따라 다르며 당첨자는 소형 어레이 삽입 정렬(47개 선택), 정렬된 어레이 대부분에 대한 병합 정렬 및 나머지 어레이에 대한 빠른 정렬입니다.그러면 Java의 Array.sort()는 이러한 기준에 따라 적용할 최적의 알고리즘을 선택합니다.

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