Как посчитать количество инверсий для большого количества входов, используя сортировку слиянием - PullRequest
Новая
       45

Как посчитать количество инверсий для большого количества входов, используя сортировку слиянием

0 голосов
/ 27 сентября 2019

Я могу рассчитывать инверсии для небольшого количества входов.Какие изменения я должен сделать, чтобы подсчитать количество инверсий для 100000 входов. 

#include<iostream>

using namespace std;

int _mergeSort(int arr[], int temp[], int left, int right);
int merge(int arr[], int temp[], int left, int mid, int right);

int mergeSort(int arr[], int array_size)
{
    int temp[array_size];
    return _mergeSort(arr, temp, 0, array_size - 1);
}

int _mergeSort(int arr[], int temp[], int left, int right)
{
    int mid, inv_count = 0;

    if (right > left)
    {
        /*Divide the array into two parts
         and call _mergeSortAndCountInv()
         for each of the parts*/

        mid = (left + right) / 2;

        /*Inversion count will be sum of inversions in left-part
         right-part as well as number of inversions while merging */

        inv_count = _mergeSort(arr, temp, left, mid); // counting inversions in the left part
        inv_count += _mergeSort(arr, temp, mid + 1, right); //counting inversions in the right part
        inv_count += merge(arr, temp, left, mid + 1, right);
    }
    return inv_count;
}

int merge(int arr[], int temp[], int left, int mid, int right)
{

    int i, j, k;
    int inv_count = 0;

    i = left; // i is the index for left subarray
    j = mid; // j is the index for right subarray
    k = right; // k is the index for resultant merged subarray

    while (i <= (mid - 1) && j <= right)
    {
        if (arr[i] < arr[j])
            temp[k++] = arr[i++];
        else
        {
            temp[k++] = arr[j++];
            inv_count = inv_count + (mid - i);
        }
    }

    // copying the remaining parts of the left subarray to temp (if any)
    while (i <= (mid - 1))
        temp[k++] = arr[i++];

    // copying the remaining parts of the left subarray to temp (if any)
    while (j <= right)
        temp[k++] = arr[j++];

    // copying back the merged elements to oroginal array ;
    for (i = left; i <= right; i++)
    {
        arr[i] = temp[i];
    }

    return inv_count;
}

int main()
{
    int arr[] = { 5, 7, 2, 3, 9, 1 };

    int n = sizeof(arr) / sizeof(arr[0]);

    int ans = mergeSort(arr, n);
    cout << "Number of inversions are" << "\n" << ans;
    return 0;
}

1 Ответ

0 голосов
/ 27 сентября 2019

k = справа;// k - индекс для результирующего объединенного подмассива

В этой строке есть проблема, я думаю, она должна быть

k = left;

Итак, проблема в алгоритме сортировки.
Слияние времени сортировки Сложность Nlog (N) И все, что вы добавили, это одна строка 

        inv_count = inv_count + (mid - i);

постоянной сложности, поэтому она не изменит общей сложности вашего алгоритма.Не будет никаких проблем при подсчете количества инверсий в массиве, даже если входные данные 100000 .

...