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.util.Arrays 는 Comparable 을 구현 하거나 Comparator를 사용하는 객체에 대해 int 및 mergesort 와 같은 기본 유형에 대해 quicksort 를 사용합니다 . 두 가지 다른 방법을 사용하는 아이디어는 프로그래머가 객체를 사용하는 경우 공간이 매우 중요한 고려 사항이 아니므로 병합 정렬에 사용되는 추가 공간 이 문제가되지 않을 수 있고 프로그래머가 기본 유형을 사용하는 경우 성능이 가장 중요한 것일 수 있으므로 사용하십시오 퀵 .
예 : 이것은 정렬 안정성이 중요한 경우의 예입니다.
그렇기 때문에 안정적인 정렬이 객체 유형, 특히 정렬 키보다 더 많은 데이터가있는 변경 가능한 객체 유형 및 객체 유형에 대해 의미가 있으며 mergesort가 그러한 정렬입니다. 그러나 원시 유형의 경우 안정성은 관련성이 없을뿐만 아니라 무의미합니다.
출처 : 정보
답변
Java의 Arrays.sort방법은 빠른 정렬, 삽입 정렬 및 병합 정렬을 사용합니다. OpenJDK 코드에 구현 된 단일 및 이중 피벗 퀵소트도 있습니다. 가장 빠른 정렬 알고리즘은 상황에 따라 다르며 승자는 작은 배열에 대한 삽입 정렬 (현재 선택한 47 개), 대부분 정렬 된 배열에 대한 병합 정렬, 나머지 배열에 대한 빠른 정렬이므로 Java의 Array.sort ()는 최상의 알고리즘을 선택하려고합니다. 해당 기준에 따라 적용됩니다.