подсчет инверсий с сортировкой слиянием дает отрицательное число, если длина массива 100000 - PullRequest
Новая
       46

подсчет инверсий с сортировкой слиянием дает отрицательное число, если длина массива 100000

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

Я все еще новичок в программировании, и я прохожу онлайн-курс (алгоритмы)

. Одним из практических вопросов было подсчет количества инверсий в файле, содержащем 100000 чисел в произвольном порядке.Я пробовал этот код на небольших наборах данных, и он работал нормально, но при передаче фактического набора данных он дает счет инверсии в отрицательном числе.Пробовал различные решения с разных платформ, но все еще не мог решить его.

, так что это мой код 

#include "stdafx.h"
#include <iostream>;
#include <conio.h>:
#include <fstream> 

using namespace std;

long merge(int a[], int start, int mid, int end) 
    int i = start; 
    int j = mid + 1; 
    int k = start; 
    int inversion=0;
    int temp[100000];

    while (i <= mid && j <= end)
    {
        if (a[i] < a[j])  
        {
            temp[k++] = a[i++]; 
        }
        else 
        {
            temp[k++] = a[j++]; 
            inversion =inversion + (mid - i);
        }
    }
    while (i <= mid) 
    {
        temp[k++] = a[i++]; 
    }
    while (j <= end) 
    {
        temp[k++] = a[j++]; 
    }

    for (int i = start; i <= end; i++)
    {
        a[i] = temp[i]; 
    }
    return inversion;

long Msort(int a[], int start,int end)
{
    if (start >= end)
    {
        return 0;
    }
    int inversion = 0;
    int mid = (start + end) / 2;

    inversion += Msort(a, start, mid);
    inversion += Msort(a, mid + 1, end); 

    inversion += merge(a, start, mid, end)
    return inversion;
}

long ReadFromFile(char FileName[], int storage[],int n)
{
    int b;
    int count=0;
    ifstream get(FileName);
    if (!get)
    {
        cout << "no file found";
    }
    while (!get.eof())
    {
        get >> storage[count];
        count++;
    }
    b = count;
    return b;
}

int main()
{
    int valuescount = 0;
    int arr[100000];
    char filename[] = { "file.txt" };
    long n = sizeof(arr) / sizeof(arr[0]);
    valuescount=ReadFromFile(filename, arr,n);
    int no_Of_Inversions = Msort(arr, 0, valuescount -1);
    cout << endl << "No of inversions are" << '\t' << no_Of_Inversions <<'\t';
    cout <<endl<< "Total no of array values sorted"<< valuescount<<endl;
    system("pause");
}
`

1 Ответ

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

Проблема с вашим кодом не связана напрямую с размером ввода.Скорее косвенным образом отрицательное число инверсий, которое вы найдете, является результатом переполнения в переменной inversion функции merge.

Рассмотрим случай для входного размера N = 100000.Если этот массив чисел отсортирован в порядке убывания, то все упорядоченные пары в этом массиве будут инверсией.Другими словами, будет учитываться N * (N-1) / 2 инверсий.Как вы могли заметить, это значение немного выше границ типа unsigned int.Следовательно, когда вы пытаетесь сосчитать это значение в переменной типа int, происходит переполнение, приводящее к отрицательному результату.

Чтобы устранить эту проблему, вы должны изменить тип переменной inversion с int до long long, в функциях merge и Msort.(Вам также следует обновить тип возвращаемого значения функций merge и Msort). Естественно, вы должны также присвоить возвращаемое значение вызова Msort в функции main переменной типа long long.Другими словами, измените тип переменной no_Of_Inversions на long long.

...