使用归并排序进行倒置计数
Counting inversion using merge sort
我知道 Stack 中有很多这样的实现,但我遇到了一个我无法处理的问题。
首先,我在 khanacademy 中使用 javascript 实现了合并排序,然后我将代码重写为 C++,并尝试计算数组中的反转次数。
我已尽我所能,并花了一个小时试图了解我做错了什么。我确实在堆栈中搜索了另一个实现并尝试更正我的代码。不幸的是我不知道我在做什么 wrong.I 认为我每次倒数。提前感谢您帮助我理解出了什么问题。
我的代码:
int lowhalflength(int p, int q)
{
return q - p + 1;
}
int highhalflength(int q, int r)
{
return r - q;
}
int merge(int array[], int p, int q, int r, int lowhalf[], int highhalf[])
{
int k = p;
int i;
int j;
int count = 0;
for (int i = 0; k <= q; i++ , k++)
{
lowhalf[i] = array[k];
}
for (int i = 0; k <= r; i++ , k++)
{
highhalf[i] = array[k];
}
k = p;
i = 0;
j = 0;
while (i <= (q - p) && j <= r - (q + 1))
{
if (lowhalf[i] <= highhalf[j])
{
array[k] = lowhalf[i];
i++;
}
else
{
array[k] = highhalf[j];
j++;
count += q - 1;
}
k++;
}
while (i < lowhalflength(p, q))
{
array[k] = lowhalf[i];
k++;
i++;
}
while (j < highhalflength(q, r))
{
array[k] = highhalf[j];
k++;
j++;
}
return count;
}
合并排序函数:
int mergeSort(int array[], int p, int r)
{
int q = ((p + r) / 2);
int* lowhalf = new int[lowhalflength(p, q)];
int* highhalf = new int[highhalflength(q, r)];
int count = 0;
if (p < r)
{
q = ((p + r) / 2);
count = mergeSort(array, p, q);
count += mergeSort(array, q + 1, r);
count += merge(array, p, q, r, lowhalf, highhalf);
}
delete[] lowhalf;
delete[] highhalf;
return count;
}
对于数组 [10, 9, 8, 7, 6, 5, 4, 3, 2, 1],输出是 46 而它应该是 45。
编辑:
答案是把下面这行q-1
改成q+j-k.
我自己找的,不知道怎么解释。任何提示或证明为什么它是正确的都是非常可取的。
您可以使用我的代码来计算反转对,您的合并函数应该以更有效的方式如下所示:
int merge(int *array, int lower, int mid, int upper) {
// Initialisation of the sizes of two subarrays and subarrays also.
int left_array_size = mid - lower + 1;
int right_array_size = upper - mid;
int left_array[left_array_size], right_array[right_array_size];
int j = 0;
for (int i = lower; i <= mid; i++) {
left_array[j++] = array[i];
}
j = 0;
for (int i = mid + 1; i <= upper; i++) {
right_array[j++] = array[i];
}
// Performing merging in a non-increasing manner and count inversion pairs..
int i = 0, k;
j = 0;
int resultIntermediate = 0;
for (k = lower; k <= upper; ) {
if (left_array[i] <= right_array[j]) {
array[k++] = left_array[i++];
if (i >= left_array_size) break;
}
else {
array[k++] = right_array[j++];
// If a element in left_array_size is greater than an element from
// right_array_size then rest of all other elements will also be
// greater than that element of right_array_size because both
// subarrays are sorted in non-decreasing order.
resultIntermediate += left_array_size - i;
if (j >= right_array_size) break;
}
} //end of for loop.
// Performing merging if i or j doesn't reach to its
// maximum value i.e. size of the subarrays.
while (i < left_array_size) {
array[k++] = left_array[i++];
}
while (j < right_array_size) {
array[k++] = right_array[j++];
}
// Returning the result...
return resultIntermediate;
} //end of the merge function.
以及计数反转对的函数
int countInversionPair(int *array, int lower, int upper) {
int count_inv_pair = 0;
// Do recusion untill the problem / array can be subdevided.
if (lower < upper) {
// Partition the Array into two subproblems.
int mid = (lower + upper) / 2;
// Call the countInversionPair() function for these two
// subarrays / subproblems recursively to count number of
// inversion for these subproblems / subarrays.
count_inv_pair = countInversionPair(array, lower, mid);
count_inv_pair += countInversionPair(array, mid + 1, upper);
// Merge these two subarrays into a sigle array
count_inv_pair += merge(array, lower, mid, upper);
}
return count_inv_pair;
}
现在您可以通过从 main 调用函数来获取反转对的数量:
int count_inv_pair = countInversionPair(array, 0, size - 1);
现在你会得到答案..
非常感谢你们所有人,尤其是@Shiv 和@WhozCraig,你们给了我解决问题的思路。答案是把q-1
改成q+j-k
我知道 Stack 中有很多这样的实现,但我遇到了一个我无法处理的问题。
首先,我在 khanacademy 中使用 javascript 实现了合并排序,然后我将代码重写为 C++,并尝试计算数组中的反转次数。
我已尽我所能,并花了一个小时试图了解我做错了什么。我确实在堆栈中搜索了另一个实现并尝试更正我的代码。不幸的是我不知道我在做什么 wrong.I 认为我每次倒数。提前感谢您帮助我理解出了什么问题。
我的代码:
int lowhalflength(int p, int q)
{
return q - p + 1;
}
int highhalflength(int q, int r)
{
return r - q;
}
int merge(int array[], int p, int q, int r, int lowhalf[], int highhalf[])
{
int k = p;
int i;
int j;
int count = 0;
for (int i = 0; k <= q; i++ , k++)
{
lowhalf[i] = array[k];
}
for (int i = 0; k <= r; i++ , k++)
{
highhalf[i] = array[k];
}
k = p;
i = 0;
j = 0;
while (i <= (q - p) && j <= r - (q + 1))
{
if (lowhalf[i] <= highhalf[j])
{
array[k] = lowhalf[i];
i++;
}
else
{
array[k] = highhalf[j];
j++;
count += q - 1;
}
k++;
}
while (i < lowhalflength(p, q))
{
array[k] = lowhalf[i];
k++;
i++;
}
while (j < highhalflength(q, r))
{
array[k] = highhalf[j];
k++;
j++;
}
return count;
}
合并排序函数:
int mergeSort(int array[], int p, int r)
{
int q = ((p + r) / 2);
int* lowhalf = new int[lowhalflength(p, q)];
int* highhalf = new int[highhalflength(q, r)];
int count = 0;
if (p < r)
{
q = ((p + r) / 2);
count = mergeSort(array, p, q);
count += mergeSort(array, q + 1, r);
count += merge(array, p, q, r, lowhalf, highhalf);
}
delete[] lowhalf;
delete[] highhalf;
return count;
}
对于数组 [10, 9, 8, 7, 6, 5, 4, 3, 2, 1],输出是 46 而它应该是 45。
编辑:
答案是把下面这行q-1
改成q+j-k.
我自己找的,不知道怎么解释。任何提示或证明为什么它是正确的都是非常可取的。
您可以使用我的代码来计算反转对,您的合并函数应该以更有效的方式如下所示:
int merge(int *array, int lower, int mid, int upper) {
// Initialisation of the sizes of two subarrays and subarrays also.
int left_array_size = mid - lower + 1;
int right_array_size = upper - mid;
int left_array[left_array_size], right_array[right_array_size];
int j = 0;
for (int i = lower; i <= mid; i++) {
left_array[j++] = array[i];
}
j = 0;
for (int i = mid + 1; i <= upper; i++) {
right_array[j++] = array[i];
}
// Performing merging in a non-increasing manner and count inversion pairs..
int i = 0, k;
j = 0;
int resultIntermediate = 0;
for (k = lower; k <= upper; ) {
if (left_array[i] <= right_array[j]) {
array[k++] = left_array[i++];
if (i >= left_array_size) break;
}
else {
array[k++] = right_array[j++];
// If a element in left_array_size is greater than an element from
// right_array_size then rest of all other elements will also be
// greater than that element of right_array_size because both
// subarrays are sorted in non-decreasing order.
resultIntermediate += left_array_size - i;
if (j >= right_array_size) break;
}
} //end of for loop.
// Performing merging if i or j doesn't reach to its
// maximum value i.e. size of the subarrays.
while (i < left_array_size) {
array[k++] = left_array[i++];
}
while (j < right_array_size) {
array[k++] = right_array[j++];
}
// Returning the result...
return resultIntermediate;
} //end of the merge function.
以及计数反转对的函数
int countInversionPair(int *array, int lower, int upper) {
int count_inv_pair = 0;
// Do recusion untill the problem / array can be subdevided.
if (lower < upper) {
// Partition the Array into two subproblems.
int mid = (lower + upper) / 2;
// Call the countInversionPair() function for these two
// subarrays / subproblems recursively to count number of
// inversion for these subproblems / subarrays.
count_inv_pair = countInversionPair(array, lower, mid);
count_inv_pair += countInversionPair(array, mid + 1, upper);
// Merge these two subarrays into a sigle array
count_inv_pair += merge(array, lower, mid, upper);
}
return count_inv_pair;
}
现在您可以通过从 main 调用函数来获取反转对的数量:
int count_inv_pair = countInversionPair(array, 0, size - 1);
现在你会得到答案..
非常感谢你们所有人,尤其是@Shiv 和@WhozCraig,你们给了我解决问题的思路。答案是把q-1
改成q+j-k