Вот код, который я написал для подсчета инверсии в C++. Если вы напишете какой-нибудь другой метод рекурсии. Пожалуйста, попробуйте объяснить это мне. Я храню счет инверсии в countI. Я получаю 2 как вывод для массива A [], который был объявлен в основной функции.Почему этот алгоритм сортировки слияния счетчиков ошибок дает неправильный ответ
#include<iostream>
#include<math.h>
using namespace std;
int countI = 0;
void merge(int A[], int p, int q, int r)
{
int n1 = q - p + 1;
int n2 = r - q;
int *L;
L = new int[n1];
int *R;
R = new int[n2];
for (int i = 1; i <= n1; i++)
{
L[i] = A[p + i - 1];
// cout << A[p + i - 1]<<endl;
//cout << L[i];
}
for (int j = 1; j <= n2; j++)
R[j] = A[q + j];
int i = 1, j = 1;
// cout << "li " << L[n1]<<"\t"<<R[n2];
for (int k = p; k <= r; k++)
{
if ((L[i] <= R[j] && i <= n1) || j>n2)
{
A[k] = L[i];
//cout << A[k];
i++;
}
else
{
A[k] = R[j];
j++;
if (i<n1)
countI += n1 - i+1; //here I am counting the inversion.
//cout <<endl<<"R"<< R[j];
}
}
}
void mergeSort(int A[], int p, int r)
{
if (p < r)
{
// cout << A[8];
int sum = p + r;
//int q = (sum)/2 + (sum % 2);
int q = (sum)/2;
mergeSort(A, p, q);
mergeSort(A, q + 1, r);
merge(A, p, q, r);
}
}
int main()
{
//I am considering array from index 1
int A[] = { 0, 1, 3, 5,2,4,6 };
// int arr[100001];
int i = 1;
int n = 0;
//while (scanf("%d", &n) != EOF) { arr[i++] = n; }
mergeSort(A, 1, 6);
for (int i = 1; i <= 6; i++)
{
cout << A[i] << " ";
}
cout << "\n " << countI;
system("pause");
return 0;
}
Вы сортируете 6 элементов. Написал каждый шаг рекурсии, проследил исходный массив и увидел, где (и когда) происходит различие. Затем перепросите свой вопрос, если вы не сможете его отладить, но я думаю, что вы это сделаете. –