使用归并计算用C倒数量++ [英] Using Mergesort to calculate number of inversions in C++
问题描述
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);
}
C中的归并参数来调用
我的第二个'B'和效果特别困惑。我需要他们在那里,所以我有机会向他们复制并和合并,但
I am specifically confused on the effect of the second 'B' and 'C' arguments in the MergeSort calls. I need them in there so I have access to them for Copy and and Merge, but
我在这里模糊道歉。下面是输出:
I apologize for the ambiguity here. Here is the output:
Input (A)= 4 2 53 8 1 19 21 6
19
19
21
19
21
19
21
6
inversions=9
显然不是为数组正确的结果,并通过我的计算,该倒应该等于16.任何帮助或意见将大大AP preciated。 (甚至批评过;!)
Obviously that is not the correct result for the array, and by my count, the inversions should equal 16. Any help or comments would be greatly appreciated. (even criticism too! ;)
推荐答案
Psuedo- code从简介算法第二版(Cormen MIT preSS):
Psuedo-code from Intro to Algorithms (Cormen. MIT Press) 2nd Edition:
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
应该注意的是实际上是不需要计算的变量。归并排序是一种固有的递归算法本质。你的实现应密切关注该psuedo- code。同时适应在必要时满足您的需求。然而,在这种情况下。直接执行这一psuedo- code会实际上是一个经典的合并排序中倒计数
One should note that the counted variable is actually not needed. Merge sort is an inherently recursive algorithm by nature. Your implementation should closely follow this psuedo-code. While adapting where necessary to suit your needs. However in this case. A direct implementation of this psuedo-code will in fact count inversions during a classic merge sort.
这篇关于使用归并计算用C倒数量++的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!