подсчет количества инверсий с использованием сортировки слиянием
я написал следующий код для подсчета количества инверсий в c ++, используя разделяй и властвуй, но он не работает, может кто-нибудь сказать мне, что здесь происходит не так? Может кто-нибудь объяснить, что не так с моим кодом, и не публиковать ссылку на любой другой связанный с этим вопрос, поскольку я прошел через них и не могу понять, что не так с моим
#include <iostream>
#include <string>
using namespace std;
int merge_count_inverse(int left[],int right[]) /*counting number of inversion using merge sort*/
{
int i=0;
int c=0;
int r=0;
int j=0;
int len_arr=0;
int len_left=(sizeof(left)/sizeof(*left));
int len_right=(sizeof(right)/sizeof(*right));
len_arr=(len_left+len_right);
int arr[len_arr];
while((i<len_left)||(j<len_right))
{
if (left[i]<right[j])
{
arr[r]=left[i];
r++;
i++;
}
if (left[i]>right[j])
{
arr[r]=right[j];
r++;
j++;
c=c+len_left-i;
}
}
return (c);
}int sort_count(int arr[])
{int cou=0;
int l=0;
int r=0;
int m=0;int len_arr=(sizeof(arr)/sizeof(*arr));
int middle=0;
middle=len_arr/2;
int left[middle];
int right[middle];if (len_arr <2)
{
return(0);
}
else
{
for (int i=0;i<=(middle-1);i++)
{
left[i]=arr[i];
right[i]=arr[middle+i];
}
l=l+sort_count(left);
r=r+sort_count(right);
m=m+merge_count_inverse(left,right);
cou=cou+l+r+m;
return(cou);
}
}
int main()
{
int arr[8]={2,5,1,3,8,7,6,9};
int len_arr=(sizeof(arr)/sizeof(*arr));int co=0;
co+=sort_count(arr);
cout<<co;
}
Решение
Я не просмотрел весь ваш код, но этого будет достаточно, чтобы указать на эту функцию sort_count является недействительным. Его параметр настроен на int * Итак, расчет len_arr не имеет смысла
int sort_count(int arr[])
{
// ...
int len_arr=(sizeof(arr)/sizeof(*arr));
На самом деле показанное утверждение эквивалентно
int len_arr=(sizeof( int * )/sizeof( int ));
Вы должны либо определить функцию как шаблонную функцию, которая имеет параметр типа ссылки на массив, либо как не шаблонную функцию, имеющую два параметра. Второй параметр будет указывать размер массива.
То же самое верно для функции merge_count_inverse
int merge_count_inverse(int left[],int right[]) /*counting number of inversion using merge sort*/
{
// ...
int len_left=(sizeof(left)/sizeof(*left));
int len_right=(sizeof(right)/sizeof(*right));
Расчеты len_left а также len_right не имеет смысла, потому что left а также right не являются массивами. Они указатели int *
Другие решения