Mergesort를 사용하여 C++에서 역변환 횟수를 계산하십시오.

Question

void MergeSort(int A[], int n, int B[], int C[]) 
{ 
    if(n > 1) 
    { 
     Copy(A,0,floor(n/2),B,0,floor(n/2)); 
     Copy(A,floor(n/2),n-1,C,0,floor(n/2)-1); 
     MergeSort(B,floor(n/2),B,C); 
     MergeSort(C,floor(n/2),B,C); 
     Merge(A,B,0,floor(n/2),C,0,floor(n/2)-1); 
    } 
}; 

void Copy(int A[], int startIndexA, int endIndexA, int B[], int startIndexB, int endIndexB) 
{ 
    while(startIndexA < endIndexA && startIndexB < endIndexB) 
    { 
     B[startIndexB]=A[startIndexA]; 
     startIndexA++; 
     startIndexB++; 
    } 
}; 

void Merge(int A[], int B[],int leftp, int rightp, int C[], int leftq, int rightq) 
//Here each sub array (B and C) have both left and right indices variables (B is an array with p elements and C is an element with q elements) 
{ 
    int i=0; 
    int j=0; 
    int k=0; 

    while(i < rightp && j < rightq) 
    { 
     if(B[i] <=C[j]) 
     { 
      A[k]=B[i]; 
      i++; 
     } 
     else 
     { 
      A[k]=C[j]; 
      j++; 
      inversions+=(rightp-leftp); //when placing an element from the right array, the number of inversions is the number of elements still in the left sub array. 
     } 
     k++; 
    } 
    if(i=rightp) 
     Copy(A,k,rightp+rightq,C,j,rightq); 
    else 
     Copy(A,k,rightp+rightq,B,i,rightp); 
} 

저는 MergeSort 호출에서 두 번째 'B'및 'C'인수의 효과에 대해 혼란스러워합니다. 내가 복사에 대한 그들에 대한 액세스 권한 및 병합, 그래서 내가 거기에서 그들을 필요하지만,

---

여기 모호성을 끼쳐 드려 죄송합니다. 그 배열에 대한 올바른 결과 아니며, 내 계산으로는 역전이 어떤 도움이나 의견이 크게 감상 할 수있다 (16)와 같아야 분명히

Input (A)= 4 2 53 8 1 19 21 6 
19 
19 
21 
19 
21 
19 
21 
6 
inversions=9 

: 여기에 출력됩니다. (심지어 비판도;!)

Answer 1

사이비 코드 소개에서 알고리즘 (Cormen MIT 키를 누릅니다.) 2 판에 :

MERGE -INVERSIONS (A, p, q, r) 
n1 ← q − p + 1 
n2 ← r − q 
create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1] 
for i ← 1 to n1 
    do L[i] ← A[ p + i − 1] 
for j ← 1 to n2 
    do R[ j ] ← A[q + j ] 
L[n 1 + 1] ← ∞ 
R[n 2 + 1] ← ∞ 
i ←1 
j ←1 
inversions ← 0 
counted ← FALSE 
for k ← p to r 
    do 
    if counted = FALSE and R[ j ] < L[i] 
    then inversions ← inversions +n1 − i + 1 
    counted ← TRUE 
    if L[i] ≤ R[ j ] 
    then A[k] ← L[i] 
    i ←i +1 
    else A[k] ← R[ j ] 
    j ← j +1 
    counted ← FALSE 
    return inversions 

하나는 계산 변수가 실제로 필요하지 않은 점에 유의해야한다. Merge sort는 기본적으로 본질적으로 재귀 적 알고리즘입니다. 귀하의 구현은이 psuedo-code를 철저히 따라야합니다. 귀하의 필요에 맞게 필요한 곳에 적응하면서. 그러나이 경우. 이 psuedo-code의 직접적인 구현은 실제로 고전적인 병합 정렬 동안의 역전을 계산합니다.