Подсчет инверсии с использованием сортировки слиянием
Я знаю, что в Stack было много таких реализаций, но у меня есть проблема, с которой я не могу справиться.
Сначала я реализовал сортировку слиянием в khanacademy с помощью javascript, затем переписал код на C ++ и попытался посчитать число инверсий в массиве.
Я сделал все, что мог, и провел час, пытаясь понять, что я сделал неправильно. Я нашел другую реализацию здесь, в стеке, и попытался исправить свой код. К сожалению, я не знаю, что я делаю неправильно. Я думаю, что я считаю каждую инверсию. Заранее спасибо за помощь, поняв, что не так.
Мой код:
int lowhalflength(int p, int q)
{
return q - p + 1;
}
int highhalflength(int q, int r)
{
return r - q;
}int merge(int array[], int p, int q, int r, int lowhalf[], int highhalf[])
{
int k = p;
int i;
int j;
int count = 0;
for (int i = 0; k <= q; i++ , k++)
{
lowhalf[i] = array[k];
}
for (int i = 0; k <= r; i++ , k++)
{
highhalf[i] = array[k];
}
k = p;
i = 0;
j = 0;
while (i <= (q - p) && j <= r - (q + 1))
{
if (lowhalf[i] <= highhalf[j])
{
array[k] = lowhalf[i];
i++;
}
else
{
array[k] = highhalf[j];
j++;
count += q - 1;
}
k++;
}
while (i < lowhalflength(p, q))
{
array[k] = lowhalf[i];
k++;
i++;
}
while (j < highhalflength(q, r))
{
array[k] = highhalf[j];
k++;
j++;
}return count;
}
Функция mergeSort:
int mergeSort(int array[], int p, int r)
{
int q = ((p + r) / 2);
int* lowhalf = new int[lowhalflength(p, q)];
int* highhalf = new int[highhalflength(q, r)];
int count = 0;
if (p < r)
{
q = ((p + r) / 2);
count = mergeSort(array, p, q);
count += mergeSort(array, q + 1, r);
count += merge(array, p, q, r, lowhalf, highhalf);
}
delete[] lowhalf;
delete[] highhalf;
return count;
}
Для массива [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] выходное значение равно 46, а должно быть 45.
РЕДАКТИРОВАТЬ:
Ответ состоит в том, чтобы изменить следующую строку q-1 в q+j-k. Я нашел это сам, но я не знаю, как мне это интерпретировать. Любой намек или доказательство, почему это правильно, будет действительно желательным.
Решение
Вы можете использовать мой код для подсчета пары инверсии, и ваша функция слияния должна выглядеть так более эффективно:
int merge(int *array, int lower, int mid, int upper) {
// Initialisation of the sizes of two subarrays and subarrays also.
int left_array_size = mid - lower + 1;
int right_array_size = upper - mid;
int left_array[left_array_size], right_array[right_array_size];
int j = 0;
for (int i = lower; i <= mid; i++) {
left_array[j++] = array[i];
}
j = 0;
for (int i = mid + 1; i <= upper; i++) {
right_array[j++] = array[i];
}
// Performing merging in a non-increasing manner and count inversion pairs..
int i = 0, k;
j = 0;
int resultIntermediate = 0;
for (k = lower; k <= upper; ) {
if (left_array[i] <= right_array[j]) {
array[k++] = left_array[i++];
if (i >= left_array_size) break;
}
else {
array[k++] = right_array[j++];
// If a element in left_array_size is greater than an element from
// right_array_size then rest of all other elements will also be
// greater than that element of right_array_size because both
// subarrays are sorted in non-decreasing order.
resultIntermediate += left_array_size - i;
if (j >= right_array_size) break;
}
} //end of for loop.// Performing merging if i or j doesn't reach to its
// maximum value i.e. size of the subarrays.
while (i < left_array_size) {
array[k++] = left_array[i++];
}
while (j < right_array_size) {
array[k++] = right_array[j++];
}
// Returning the result...
return resultIntermediate;
} //end of the merge function.
И функция для подсчета пары инверсии
int countInversionPair(int *array, int lower, int upper) {
int count_inv_pair = 0;
// Do recusion untill the problem / array can be subdevided.
if (lower < upper) {
// Partition the Array into two subproblems.
int mid = (lower + upper) / 2;
// Call the countInversionPair() function for these two
// subarrays / subproblems recursively to count number of
// inversion for these subproblems / subarrays.
count_inv_pair = countInversionPair(array, lower, mid);
count_inv_pair += countInversionPair(array, mid + 1, upper);
// Merge these two subarrays into a sigle array
count_inv_pair += merge(array, lower, mid, upper);
}
return count_inv_pair;
}
Теперь вы можете получить номер пары инверсии, вызвав функцию из main как:
int count_inv_pair = countInversionPair(array, 0, size - 1);
И теперь вы получите свой ответ ..
Другие решения
Большое спасибо всем вам, ребята, особенно @Shiv и @WhozCraig, вы дали мне идею и как ее решить. Ответ должен изменить q-1 в q+j-k
detector