Значение числа инверсий инверсии в сортировке слиянием
Ниже приведен код для подсчета инверсий в массиве. У меня есть сомнения в этой части:
inv_count = _mergeSort(arr, temp, left, mid);--i
inv_count += _mergeSort(arr, temp, mid+1, right);--ii
inv_count += merge(arr, temp, left, mid+1, right);--iii
При подсчете инверсии полная инверсия будет равна i + ii + iii, но я не могу понять, как «inv_count из i и ii даже получает значение, они вызываются рекурсивно и заполняются в стеке функций, но нигде не имеют значения передается inv_count
для i и ii, хотя в iii, inv_count получает значение, используя invcount = inv_count + mid-i;
int mergeSort(int arr[], int array_size)
{
int *temp = (int *)malloc(sizeof(int)*array_size);
return _mergeSort(arr, temp, 0, array_size - 1);
}
/* An auxiliary recursive function that sorts the input array and
returns the number of inversions in the array. */
int _mergeSort(int arr[], int temp[], int left, int right)
{
int mid, inv_count = 0;
if (right > left)
{
/* Divide the array into two parts and call _mergeSortAndCountInv()
for each of the parts */
mid = (right + left)/2;
/* Inversion count will be sum of inversions in left-part, right-part
and number of inversions in merging */
inv_count = _mergeSort(arr, temp, left, mid);
inv_count += _mergeSort(arr, temp, mid+1, right);
/*Merge the two parts*/
inv_count += merge(arr, temp, left, mid+1, right);
}
return inv_count;
}
/* This funt merges two sorted arrays and returns inversion count in
the arrays.*/
int merge(int arr[], int temp[], int left, int mid, int right)
{
int i, j, k;
int inv_count = 0;
i = left; /* i is index for left subarray*/
j = mid; /* i is index for right subarray*/
k = left; /* i is index for resultant merged subarray*/
while ((i <= mid - 1) && (j <= right))
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
/*this is tricky -- see above explanation/diagram for merge()*/
inv_count = inv_count + (mid - i);
}
}
/* Copy the remaining elements of left subarray
(if there are any) to temp*/
while (i <= mid - 1)
temp[k++] = arr[i++];
/* Copy the remaining elements of right subarray
(if there are any) to temp*/
while (j <= right)
temp[k++] = arr[j++];
/*Copy back the merged elements to original array*/
for (i=left; i <= right; i++)
arr[i] = temp[i];
return inv_count;
}
Решение
Вот рабочий код для подсчета инверсии .— i —ii —iii не имеет никакого отношения к счету инверсии.
Общее число инверсий во время сортировки слиянием равно сумме инверсий, полученных при сортировке левой части и сортировке правой части и объединении левой части с правой частью. Если вам не понятен код, тогда, пожалуйста, оставьте комментарий.
#include <iostream>
#include <stdio.h>
#include <limits.h>
#include <algorithm>
using namespace std;
const int size = 1000000;
long long int array[size];
long long int merge(long long int a[], long long int beg, long long int mid,
long long int end) {
long long int inverse = 0;
long long int lsize = (mid - beg) + 1;
long long int rsize = (end - mid);
long long int left[lsize + 1];
long long int right[rsize + 1];
long long int i;
long long int j = beg;
for (i = 0; i < lsize; ++i, ++j) {
left[i] = a[j];
}
j = mid + 1;
for (i = 0; i < rsize; ++i, ++j) {
right[i] = a[j];
}
left[lsize] = LONG_LONG_MAX;
right[rsize] = LONG_LONG_MAX;
j = 0;
i = 0;
for (int k = beg; k <= end; ++k) {
if (left[i] <= right[j]) {
a[k] = left[i];
++i;
} else {
a[k] = right[j];
inverse += (lsize - i);
++j;
}
}
return inverse;
}
long long int merge_sort(long long int iArray[], long long int beg,
long long int end) {
if (beg < end) {
long long int mid;
long long int left = 0;
long long int right = 0;
long long int total = 0;
mid = (beg + end) / 2;
left = merge_sort(iArray, beg, mid);
right = merge_sort(iArray, mid + 1, end);
total = merge(iArray, beg, mid, end);
return left + right + total;
} else {
return 0;
}
}
Другие решения
Других решений пока нет …