Почему этот алгоритм сортировки слиянием счетчиков инверсий дает неправильный ответ
Вот код, который я написал для подсчета инверсии в 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;
}
Решение
Вы должны заметить, что C ++ использует массивы с индексами 0.
Первым элементом L и R являются 0, а не 1.
То же самое, когда вы вызываете mergeSort в вашей основной.
попробуйте mergeSort (A, 0, 5)
Хотя вы согласны с ошибкой индексации, начинающейся с 1. Вы запускаете конец своих массивов на 1. Это может привести к сбою вашей программы; однако, когда это не так, вы часто получаете странные ответы (которые трудно отладить), потому что вы неправильно обращаетесь и пишете в память.
Вот некоторый псевдокод (для 0 индексированных массивов), который будет считать инверсии при выполнении сортировки слиянием.
merge(A, p, m , q){
B = [] // array size of q - p + 1
i = p, j = m+1, k = 0, inv = 0
while (i <= m && j <= q){
if (A[i] < A[j])
B[k++] = A[i++]
else{
B[k++] = A[j++]
inv += m - i + 1
}
}
while (i <= m) // copy rest of left side to temp array
B[k++] = A[i++] // otherwise it may be overwritten
i = 0;
while (i < k){ // copy temp array elements back to A
A[p+i] = B[i]
++i
}
return inv
}
merge_sort(A, p, q){
if (p == q)
return 0;
m = floor((p + q)/2)
inv1 = merge_sort(A, p, m)
inv2 = merge_sort(A, m+1, q)
return inv1 + inv2 + merge(A, p, m, q)
}
// you can call it like this:
A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} // 10 Elements
inversions = merge_sort(A, 0, 9) // sort and count inversions from index 0 to index 9
Другие решения