Mon algorithme de tri de fusion prend trop de temps pour une entrée de fichier volumineux? - c ++, algorithme, complexité temporelle, mergesort, divide and conquer

Eh bien, c’est pas vraiment une sorte de fusion, l’algorithmecompte le nombre d'inversions dans un tableau en utilisant le tri par fusion (en gros, je viens d'ajouter une simple ligne) il faut 2,415 secondes pour lire et fusionner le tri de 100 000 entiers distincts à partir d'un fichier texte, tandis que d'autres personnes ayant résolu le même problème (sur coursera.com) ont déclaré qu'il leur avait fallu moins de 0,5 seconde

voici mon code, qu'est-ce qui ne va pas? lecture du fichier peut-être? merci

#include <bits/stdc++.h>

using namespace std;
int a,b,i,j,n,x,k;
int t[100000]={0};
long long int s=0;

void merge(int a, int mid, int b)
{
i=a;
j=mid+1;
k=a;
int v[100000]={0};
while(i<=mid && j<= b)
{
if (t[i]<t[j])
{v[k]=t[i];
i++;
}
else
{v[k]=t[j];
j++;
s+=mid-i+1; //this line here counts the inversions
}
k++;
}
while(i<=mid)
{v[k]=t[i];
i++; k++;}

while(j<=b)
{v[k]=t[j];
j++; k++;}

for (i=a;i<k;i++)
t[i]=v[i];
}


void mergeSort(int a, int b)
{
if(a<b)
{
int mid=(a+b)/2;
mergeSort(a,mid);
mergeSort(mid+1,b);
merge(a,mid,b);
}
}


int main(){
ifstream fin("C:\Users\ASUS\Desktop\coursera.txt");
n=100000;
for(i=0;i<n;i++)
fin>>t[i];

mergeSort(0,n-1);

cout<<endl<<s;

}

Réponses:

Un problème que j'ai pu voir est que dans la fonction de fusion,vous allouez trop d’espace, et la copie en retour prend également assez de O (N), ce qui donne le temps total de copie O (N * N) au lieu de O (N * Log (N)). Un simple changement à la fonction de fusion pourrait ressembler à:

void merge(int a, int mid, int b)
{
i = a;
j = mid + 1;
k = 0;
int* v = new int[b - a + 1];
while (i <= mid && j <= b)
{
if (t[i]<t[j])
{
v[k] = t[i];
i++;
}
else
{
v[k] = t[j];
j++;
s += mid - i + 1; //this line here counts the inversions
}
k++;
}
while (i <= mid)
{
v[k] = t[i];
i++; k++;
}

while (j <= b)
{
v[k] = t[j];
j++; k++;
}

for (i = 0; i<k; i++)
t[a+i] = v[i];

delete[] v;
v = NULL;
}