비율 확장 정렬
Proportion extend sort| 클래스 | 정렬 알고리즘 |
|---|---|
| 데이터 구조 | 배열 |
| 최악의 경우 공연 | O(n log n) |
| 베스트 케이스 공연 | O(n log n) |
| 평균 공연 | O(n log n) |
| 최악의 경우 공간 복잡성 | O(log n) 보조 |
비율 확장 정렬(약칭 PESort)은 성능, 특히 최악의 경우 성능 향상을 시도하는 퀵소트의 내부 비교 기반 정렬 알고리즘이다.
퀵소트의 기본 분할 연산은 선형 접근 패턴을 가지고 있어 현대 메모리 계층 구조에서 매우 효율적이지만 알고리즘의 성능은 피벗 값의 선택에 따라 결정적으로 좌우된다.좋은 피벗은 데이터를 거의 동일한 절반으로 나눌 것이다.선택이 잘 안되면 한 부분이 거의 원래의 문제만큼 크게 남아서 O(n2) 성능을 유발하는 엄청나게 편중된 분할이 초래될 것이다.
비율 확장 정렬은 k 요소의 정렬된 접두사로 시작한 다음 해당 표본의 중위수를 사용하여 다음 pk 요소를 분할한다.표본과 분할되는 데이터 사이의 크기 비율 p(즉, 정렬된 접두사가 확장되는 비율)를 제한하여 불균형을 제한한다.이 점에서, 그것은 견본과 약간의 유사성을 가지고 있다.[1]
역사
비례 확장 분류는 Chung-Chao Chen에 의해 2001년에[2] 그의 초기 비율 분할 분류 설계의 개선으로 출판되었다.[3]원본 논문에서만 실험적으로 측정했던 평균 사례 성능은 2004년[4] 리처드 콜과 데이비드 C. 칸다틸, 2006년 첸이 분석했으며 평균적으로 logn2 + O(n) 비교가 필요한 것으로 나타났다.[5]약간 정제된 변종인 대칭 분할 분류는 2007년에 출판되었다.[6]
알고리즘.
알고리즘은 정렬되지 않은 부분 U에 인접한 정렬된 부분 S로 분할된 배열로 시작한다. (정렬되지 않은 부분보다 정렬된 부분이 항상 앞에 있고 대칭 변형이 어느 한 순서를 허용한다.)정렬된 부분(단일 요소는 항상 정렬됨)으로 첫 번째 요소부터 시작하거나, 간단한 삽입 정렬을 사용하여 적은 수의 요소를 정렬할 수 있다.또한 사전에 정렬된 데이터의 경우 성능을 향상시키기 위해 배열 전체에서 초기 정렬된 요소를 가져올 수 있다.
다음으로, 그리고 가장 비판적으로, 정렬되지 않은 부분 U의 길이는 정렬된 부분 S의 길이의 복수 p로 제한된다. 특히, U > p2 S, 그 다음에 반복적으로 S와 인접한 U의 p S 요소를 정렬하여 결과(p[a]+1배 더 길다)를 새로운 S로 만들고, 조건이 충족될 때까지 반복한다.
변형되지 않은 부분(p=csv)에 제한이 없다면 알고리즘은 퀵소트(quicksort)에 해당한다.정렬되지 않은 부분이 길이 1(p=0, 거의)인 경우 알고리즘은 이진 삽입 정렬과 동일하다.p≈16 주변의 값은 퀵소트(quicksort)와 경쟁적으로 최상의 평균 사례 성능을 제공하는 반면,[6]: 764 작은 값은 최악의 경우 성능을 향상시킨다.[b]
Eliezer Albacea는 1995년에 Leapfroging samplesort라는 유사한 알고리즘을 발표했는데, 크기가 제한되어 U ≤ S +1로 나중에 (2-1k)(S +1)로 일반화되었다.[7][1][8]
배열의 정렬된 부분은 (중앙값에서) 반으로 나누어져 있고, 절반은 (변형되지 않은 요소와 교환하여) 배열의 맨 끝으로 이동하기 때문에 초기 부분분할된 LUR 형식의 배열이 있는데, 여기서 L은 정렬된 부분의 왼쪽 반이고, U는 경계 길이 미변형 부분이고, R은 정렬된 파의 오른쪽 반이다.t
그런 다음 U에서 표준 퀵소트 분할 단계를 수행하여 U와L U로RL 나누며R(제자리에) 정렬하지 않지만 U의L 모든 요소가 중위수 이하 또는 같으며 U의R 모든 요소가 더 크거나 같다.[c]최종 결과 LUR는LR 필요한 형태의 두 배열(변형되지 않은 부품에 인접한 정렬된 부품)으로 구성되며 반복적으로 정렬된다.
Leapfrogging samplesort고 원본 비율은 정렬된 부분인 침은 항상 정리되지 않은 부분, R이사 가기 전에 U분할로 달성하 LRULUR게 되었고, 그때 UL의 끝을 만지작거리더니 LULRUR의 결과 R를 교환하는 선행이 뻗어 있다.반면 대칭 버전은 비트 trickier, 그것은 L그리고 R부분 감시인으로 행동하는 장점이 있다.U의 한계에 도달했는지 여부를 테스트할 필요 없이 분할 루프에 대한 값.[1]
주로 편향된 입력을 검출하고 효율적으로 처리하는 기법을 포함해 퀵소트에 사용되는 구현 개선의 대부분을 적용할 수 있다.[9][6]특히 특정 크기 임계값 미만의 하위 정렬은 보통 간단한 삽입 정렬을 사용하여 구현된다.
퀵소트(quicksort)와 마찬가지로 작은 서브소트(sub-sort)를 먼저 하고 큰 것을 테일콜(tail call)로 구현하면 재귀적 레벨의2 수를 logn(로그인)으로 제한할 수 있다.퀵소트와 달리 레벨 수는 이렇게 하지 않아도 O(log n)로 경계를 이룬다.[9]: 781
메모들
참조
- ^ a b Albacea, Eliezer A. (January 2012). "Average-case analysis of Leapfrogging samplesort" (PDF). Philippine Science Letters. 5 (1).
- ^ Chen, Jing-Chao (July 2001). "Proportion extend sort". SIAM Journal on Computing. 31 (1): 323–330. doi:10.1137/S0097539798342903.
- ^ Chen, Jing-Chao (Fall 1996). "Proportion split sort". Nordic Journal of Computing. 3 (3): 271–279. doi:10.1137/S0097539798342903.
- ^ Cole, Richard; Kandathil, David C. (14–17 September 2004). The Average Case Analysis of Partition Sorts (PDF). Algorithms—ESA 2004: 12th Annual European Symposium. Bergen. pp. 240–251. doi:10.1007/978-3-540-30140-0_23. ISBN 3-540-23025-4.
- ^ Chen, Jing-Chao (15 December 2006). "Efficient sample sort and the average case analysis of PEsort". Theoretical Computer Science. 369 (1–3): 44–66. doi:10.1016/j.tcs.2006.07.017.
- ^ a b c Chen, Jing-Chao (11 September 2007). "Symmetry Partition Sort". Software: Practice and Experience. 38 (7): 761–773. arXiv:0706.0046. doi:10.1002/spe.851. S2CID 844616.
- ^ Albacea, Eliezer A. (1995). Leapfrogging samplesort. Asian Computing Science Conference. doi:10.1007/3-540-60688-2_30.
- ^ Albacea, Eliezer A. (29 January 2018). "Generalized Leapfrogging Samplesort: A Class of O(n log22 n) Worst-Case Complexity and O(n log n) Average-Case Complexity Sorting Algorithms". arXiv:1801.09431 [cs.DS].
- ^ a b Chen, Jing-Chao (10 July 2004). "Building a new sort function for a C library". Software: Practice and Experience. 34 (8): 777–795. doi:10.1002/spe.593. S2CID 8193225.
