Подсчет инверсий в векторе с использованием Mergesort Stack Overflow

Question

Подсчет инверсий в векторе с использованием Mergesort Stack Overflow

Алгоритм возвращает отключение на одну ошибку для некоторых входов, которые я ему отправляю. Сначала я написал merge_sort и inversion_count с массивом; который вернул правильное количество инверсий. Как только я перешел на векторы, я получаю по одному для следующего ввода:
2 4 1 3 5

Свежая пара глаз будет оценена.

vector<int> a;
object o;

length = a.size();
inv = o.count_inversion(a, 0, length-1);int inversion::merge_and_count(vector<int> vector1, int alpha, int omega)
{
int inversion = 0;
int mid = (alpha + omega) / 2;
int i = alpha;
int j = mid + 1;
int lastITR = 0;
vector<int> final(omega - alpha + 1);while (i <= mid && j <= omega) {
if (vector1[i] <= vector1[j])
{
final[lastITR++] = vector1[i++];
}
else
{
final[lastITR++] = vector1[j++];
inversion += mid - i + 1;
}
}

while (i <= mid)
{
{
final[lastITR++] = vector1[i++];
}

while (j <= omega)
{
final[lastITR++] = vector1[j++];
}

for (int k=0 ; k < omega-alpha+1; k++)
{
vector1[k+alpha] = final[k];
}

return inversion;
}int inversion::count_inversion(vector<int> vector1, int a, int b)
{
int x, y, z, mid;

if (a >= b)
{
return 0;
}

mid = (a+b)/2;

x = count_inversion(vector1, a, mid);
y = count_inversion(vector1, mid+1, b);
z = merge_and_count(vector1, a, b);

return x + y + z;
}

1

c++inversion mergesort vector

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Ниже приведена одна причина, которая может вызвать вашу проблему (примечание: я понятия не имею, что вы пытаетесь сделать, но я не думаю, что это действительно имеет значение):

int inversion::merge_and_count(vector<int> vector1, int alpha, int omega)
// note: pass by *value*, not reference ------^

Очевидно, вы намереваетесь изменить этот вектор для вызывающей стороны, потому что в конце вашей процедуры:

for (int k=0 ; k < omega-alpha+1; k++)
{
vector1[k+alpha] = final[k];
}

По сути, вы строите объединенный final, а затем скопировать его в вектор, который собирается быть уничтоженным. Сторона звонящего vector<int> не тронут, когда это сделано, оставаясь таким же, как это было раньше.

Исправьте это, используя ссылку:

int inversion::merge_and_count(vector<int>& vector1, int alpha, int omega)
// note: reference -----------------------^

Есть некоторые потенциальные проблемы, но это, вероятно, та, которая приносит вам горе. Передача по стоимости в count_inversion должно быть в порядке, так как не ясно, хотите ли вы изменить вектор вызывающего абонента, и если это только подсчет инверсий, вы, вероятно, не хотите. Но merge_and_count Нужно использовать ссылку.

Примечание: как только вы изучите итераторы, вы с радостью будете использовать их для моделирования чего-то подобного. Это делает код не только чище, но и автоматически позволяет использовать его в любом контейнере последовательностей, поддерживающем правильный тип итератора.

2