stl __merge_without_buffer 알고리즘?

Question

사용 된 알고리즘에 대한 적절한 고급 설명은 어디에서 얻을 수 있습니까? __merge_without_buffer() C ++ STL에서? 나는이 코드를 D 프로그래밍 언어로 상환하려고 노력하고 있습니다. STL 소스 코드를 읽는 것만으로도 알고리즘 수준에서 수행하는 일을 모호하게하는 것 같습니다. 또한 코드를 맹목적으로 번역하고 싶지 않습니다. 그렇지 않으면 왜 작동하지 않으면 왜 그런지 알 수없고 내 향상을 추가 할 수 없기 때문입니다.

Answer 1

__merge_without_buffer() 수행 중입니다 내내 병합, 내 위치의 병합 단계가 정렬을 병합합니다. 두 개의 데이터 범위의 데이터를 입력하는 데 걸립니다 [first, middle) 그리고 [middle, last) 이미 정렬 된 것으로 가정합니다. 그만큼 len1 그리고 len2 매개 변수는 두 입력 범위의 길이, 즉 (middle - first) 그리고 (last - middle) 각기.

먼저, 그것은 a를 선택합니다 피벗 요소. 그런 다음 데이터를 순서로 재 배열합니다 A1 B1 A2 B2, 어디 A1 요소 세트입니다 [first, middle) 피벗보다 작습니다. A2 요소 세트입니다 [first, middle) 피벗보다 크거나 동일합니다. B1 요소 세트입니다 [middle, last) 피벗보다 적습니다 B2 요소 세트입니다 [middle, last) 피벗보다 크거나 동일합니다. 데이터는 원래 순서입니다 A1 A2 B1 B2, 우리가해야 할 일은 A2 B1 ~ 안으로 B1 A2. 이것은 전화를받습니다 std::rotate(), 그것은 바로 그렇게합니다.

이제 우리는 피벗보다 적은 요소를 분리했습니다 (A1 그리고 B1) 피벗보다 크거나 같은 것들 (A2 그리고 B2), 이제 우리는 두 개의 해적을 재귀 적으로 병합 할 수 있습니다. A1 A2 그리고 B1 B2.

피벗을 어떻게 선택합니까? 내가보고있는 구현에서, 그것은 더 큰 서브 랜지에서 중간 요소를 선택합니다 (예 : [first, middle) 보다 더 많은 요소가 있습니다 [middle, last), 그것은 중앙값을 선택합니다 [first, middle); 그렇지 않으면 중앙값을 선택합니다 [middle, last)). 서브랑이 이미 분류되었으므로 중앙값을 선택하는 것은 사소한 일입니다. 이 피벗 선택은 두 개의 서브랑을 재귀 적으로 병합 할 때 각 하위 문제가 현재 문제의 크기의 3/4를 넘지 않도록합니다. 최악의 경우 요소의 최소 1/4 이상이 피벗보다 크거나 작기 때문입니다. .

이것의 실행 시간은 얼마입니까? 그만큼 std::rotate() 통화는 O (n) 시간이 걸리며 우리는 우리 자신에게 두 번의 재귀적인 전화를합니다. 이것은 O (n log n)의 실행 시간과 동일합니다. 그러나 이것은 Mergesort의 한 단계 일뿐입니다. Mergesort에서 먼저 두 절반을 재귀 적으로 정렬 한 다음 병합한다는 점을 기억하십시오. 따라서 Mergesort의 실행 시간에 대한 재발 관계는 이제 다음과 같습니다.

T(N) = 2T(N/2) + O(N log N)

이것을 마스터 정리, 그리고 당신은 이제 MERGESTORT가 O (n log에서 실행됩니다.² n) 시간!

흥미로운 마지막 요점으로, 비교 기반 분류 알고리즘의 다음 세 가지 특성을 고려하십시오.

1. 현장
2. 안정적인
3. O (n log n) 시간으로 실행됩니다

일반적으로 한 번에 2 개만 얻을 수 있습니다. QuickSort는 (1)과 (3)을 얻고, Mergesort는 (2)와 (3)을 얻고 내장 Mergesort는 (1)과 (2)을 얻습니다. 카운트 정렬과 같은 비교 기반 종류는 3 가지를 모두 달성 할 수 있지만 이러한 종류는 특정 데이터 유형 만 정렬 할 수 있습니다. 3 개를 모두 달성하는 비교 기반 정렬이있을 수 있지만, 있다면, 나는 그 존재를 알지 못하고 거의 더 복잡합니다.