이중 피벗 퀵 정렬과 퀵 정렬의 차이점은 무엇입니까?

이중 피벗 퀵 정렬과 퀵 정렬의 차이점은 무엇입니까?

---

전에 듀얼 피벗 퀵 정렬을 본 적이 없습니다. 빠른 정렬의 업그레이드 버전 인 경우?
그리고 듀얼 피벗 퀵 정렬과 퀵 정렬의 차이점은 무엇입니까?

---

나는 이것을 자바 문서에서 찾을 수있다.

정렬 알고리즘은 Vladimir Yaroslavskiy, Jon Bentley 및 Joshua Bloch의 Dual-Pivot Quicksort입니다. 이 알고리즘은 많은 데이터 세트에서 O (n log (n)) 성능을 제공하여 다른 빠른 정렬이 2 차 성능으로 저하되도록하며 일반적으로 기존 (1 피벗) Quicksort 구현보다 빠릅니다.

그런 다음 Google 검색 결과에서 이것을 찾습니다. 빠른 정렬 알고리즘의 Thoery :

1. 배열에서 피벗이라고하는 요소를 선택합니다.
2. 피벗보다 작은 모든 요소가 피벗 앞에오고 피벗보다 큰 모든 요소가 그 뒤에 오도록 배열을 재정렬하십시오 (동일한 값은 어느 쪽이든 갈 수 있음). 이 분할 후 피벗 요소는 최종 위치에 있습니다.
3. 작은 요소의 하위 배열과 큰 요소의 하위 배열을 재귀 적으로 정렬합니다.

이에 비해 이중 피벗 빠른 정렬 :

( )

1. 작은 배열 (길이 <17)의 경우 삽입 정렬 알고리즘을 사용합니다.
2. 두 개의 피벗 요소 P1과 P2를 선택합니다. 예를 들어 첫 번째 요소 a [left]를 P1로, 마지막 요소 a [right]를 P2로 가져올 수 있습니다.
3. P1은 P2보다 작아야합니다. 그렇지 않으면 스왑됩니다. 따라서 다음 부분이 있습니다.
   • P1보다 작은 요소가있는 왼쪽 +1부터 L-1까지의 인덱스가있는 파트 I,
   • P1보다 크거나 같고 P2보다 작거나 같은 요소가있는 L에서 K-1까지의 인덱스가있는 파트 II,
   • P2보다 큰 요소가있는 G + 1에서 오른쪽 -1까지의 인덱스가있는 파트 III,
   • 파트 IV에는 K에서 G까지의 인덱스로 조사 할 나머지 요소가 포함되어 있습니다.
4. 파트 IV의 다음 요소 a [K]는 두 개의 피벗 P1 및 P2와 비교되고 해당 파트 I, II 또는 III에 배치됩니다.
5. 포인터 L, K 및 G가 해당 방향으로 변경됩니다.
6. 4-5 단계는 K ≤ G 동안 반복됩니다.
7. 피벗 요소 P1은 파트 I의 마지막 요소와 교체되고, 피벗 요소 P2는 파트 III의 첫 번째 요소와 교체됩니다.
8. 1 ~ 7 단계는 모든 파트 I, 파트 II 및 파트 III에 대해 반복적으로 반복됩니다.

---

관심이있는 분들은 Java에서이 알고리즘을 구현 한 방법을 살펴보십시오.

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/DualPivotQuicksort.java#DualPivotQuicksort.sort%28int%5B%5D%2Cint%2Cint% 2Cint % 5B % 5D % 2Cint % 2Cint % 29

출처에 명시된 바와 같이 :

"가능한 경우 병합을 위해 주어진 작업 공간 배열 슬라이스를 사용하여 배열의 지정된 범위를 정렬합니다.

이 알고리즘은 많은 데이터 세트에서 O (n log (n)) 성능을 제공하여 다른 빠른 정렬이 2 차 성능으로 저하되도록하며 일반적으로 기존 (1 피벗) Quicksort 구현보다 빠릅니다. "

---

알고리즘 관점에서 추가하고 싶습니다 (예 : 비용은 비교 및 ​​스왑 수만 고려), 2 피봇 퀵소트 및 3 피봇 퀵소트는 기존 퀵소트 (1 피봇 사용)보다 낫지 않습니다. 보다 나쁜. 그러나 현대 컴퓨터 아키텍처의 이점을 취하기 때문에 실제로는 더 빠릅니다. 특히 캐시 미스 수가 적습니다. 따라서 모든 캐시를 제거하고 CPU와 메인 메모리 만 있으면 2 / 3-pivot quicksort가 기존 quicksort보다 나쁩니다.

참조 : 3 피벗 퀵소트 : https://epubs.siam.org/doi/pdf/10.1137/1.9781611973198.6 기존 퀵소트보다 더 나은 성능을 발휘하는 이유 분석 : https://arxiv.org/pdf/1412.0193v1.pdf 너무 많지 않은 완전한 참조 : https://algs4.cs.princeton.edu/lectures/23Quicksort.pdf

참조 URL : https://stackoverflow.com/questions/20917617/whats-the-difference-of-dual-pivot-quick-sort-and-quick-sort